&＃xff08;点击此处查看原题&＃xff09;
题意&＃xff1a;有n个人&＃xff0c;编号记为1~n&＃xff0c;n个人之间可能有人可以互相联系&＃xff0c;如果A能和B联系&＃xff0c;那么至少满足这两种情况之一&＃xff1a;&＃xff08;1&＃xff09;A知道B的电话&＃xff08;2)A可以和C联系&＃xff0c;并且C可以和B联系&＃xff1b;
因为某些人可能会丢失他的手机&＃xff0c;导致他失去所有人的号码以及其他人手机中他的号码&＃xff0c;也就是说这个人无法和任何人联系了&＃xff1b;
此时给出两个人s,t&＃xff0c;问至少有多少人失去他们的手机&＃xff0c;可以使得这两个人s,t无法联系。
答案输出最少需要的人数以及失去手机的人的编号&＃xff0c;如果存在多组解&＃xff0c;输出字典序小的那一组。
思路&＃xff1a;平时写的最小割问题是求边割集&＃xff0c;这个题题目求的是最小点割集&＃xff0c;对于这类题目我们采用如下建边方法&＃xff1a;
1&＃xff09;将每个人代表的结点拆成两个结点&＃xff0c;记编号1~n为入点&＃xff0c;n&＃43;1~2*n为出点&＃xff0c;由入点向出点建一条容量为1的边
2&＃xff09;对于可以联系的两人 a,b&＃xff0c;由a的出点向b的入点建一条容量为inf的边&＃xff0c;并由b的出点向a的入点建一条容量为inf的边
3&＃xff09;由于源点就是某个人&＃xff0c;那么我们将这个人的出点当作源点
建好边之后&＃xff0c;我们跑一遍最大流&＃xff08;最小割&＃xff09;就可以得到最小点割集
个人认为这个题主要麻烦在输出割点&＃xff0c;我的方法是不断地的删点&＃xff0c;如果删去这一点后得到的最大流大于删这点之前的最大流&＃xff0c;那么这个点就是割点&＃xff0c;为保证字典序最小&＃xff0c;因而从1开始枚举割点
#include#include#include#include#include#include<string>#include#include#include#include #include #define bug cout <<"**********" <#define show(x, y) cout<<"["<#define LOCAL &＃61; 1;using namespace std;typedef long long ll;const int inf &＃61; 0x3f3f3f3f;const ll mod &＃61; 998244353;const int Max &＃61; 1e5 &＃43; 10;const int Max2 &＃61; 1e3 &＃43; 10;struct Edge{int to, flow, next;} edge[Max <<1];int n, s, t;int head[Max2], tot;int dis[Max2];bool vis[210][210], cancel[210];int id[Max2], cnt;void init(){memset(head, -1, sizeof(head));tot &＃61; 0;}void add(int u, int v, int flow){edge[tot].to &＃61; v;edge[tot].flow &＃61; flow;edge[tot].next &＃61; head[u];head[u] &＃61; tot&＃43;&＃43;;}void build(){init();for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){if (!cancel[i]){add(i, i &＃43; n, 1);add(i &＃43; n, i, 0);}}for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){for (int j &＃61; 1; j <&＃61; n; j&＃43;&＃43;){if(vis[i][j]){add(i &＃43; n, j, inf);add(j, i &＃43; n, 0);}}}}bool bfs(){memset(dis, -1, sizeof(dis));queue<int> q;q.push(s);dis[s] &＃61; 0;while (!q.empty()){int u &＃61; q.front();q.pop();for (int i &＃61; head[u]; i !&＃61; -1; i &＃61; edge[i].next){int v &＃61; edge[i].to;if (edge[i].flow > 0 && dis[v] &＃61;&＃61; -1){dis[v] &＃61; dis[u] &＃43; 1;if (v &＃61;&＃61; t)return true;q.push(v);}}}return false;}int dfs(int u, int flow_in){if (u &＃61;&＃61; t)return flow_in;int flow_out &＃61; 0;for (int i &＃61; head[u]; i !&＃61; -1; i &＃61; edge[i].next){int v &＃61; edge[i].to;if (edge[i].flow > 0 && dis[v] &＃61;&＃61; dis[u] &＃43; 1){int flow &＃61; dfs(v, min(flow_in, edge[i].flow));if (flow &＃61;&＃61; 0)continue;flow_in -&＃61; flow;flow_out &＃43;&＃61; flow;edge[i].flow -&＃61; flow;edge[i ^ 1].flow &＃43;&＃61; flow;if (flow_in &＃61;&＃61; 0)break;}}return flow_out;}int Dinic(){int sum &＃61; 0;while (bfs()){sum &＃43;&＃61; dfs(s, inf);}return sum;}int main(){#ifdef LOCAL//freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);#endifwhile (scanf("%d%d%d", &n, &s, &t) !&＃61; EOF){memset(cancel, 0, sizeof(cancel));memset(vis, 0, sizeof(vis));cnt &＃61; 0;for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){for (int j &＃61; 1,x; j <&＃61; n; j&＃43;&＃43;){scanf("%d", &x);vis[i][j] &＃61; x;}}if(vis[s][t]) //s,t可以直接联系&＃xff0c;那就不存在最小割了 {printf("NO ANSWER!\n");continue;}s &＃43;&＃61; n;build();int min_cost &＃61; Dinic();printf("%d\n", min_cost);if (min_cost &＃61;&＃61; 0)continue;int last &＃61; min_cost;for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){if (i &＃43; n &＃61;&＃61; s || i &＃61;&＃61; t)continue;cancel[i] &＃61; true;build();int temp &＃61; Dinic();if (temp //相比于不删除i点&＃xff0c;删除i点之后最大流减少&＃xff0c;则此点为割点 {id[&＃43;&＃43;cnt] &＃61; i;last--;if (cnt &＃61;&＃61; min_cost)break;}else{cancel[i] &＃61; false;}}for (int i &＃61; 1; i )printf("%d ", id[i]);printf("%d\n", id[cnt]);}return 0;}
转:https://www.cnblogs.com/winter-bamboo/p/11384939.html
京公网安备 11010802041100号