题目链接：http://poj.org/problem?id=1815

题意：A与B能通信当且仅当A知道B的电话号或者A知道C的电话号且C与B能通信。若A知道B的电话号，那么B也知道A的电话号。

然而不好的事情总会发生在某些人身上，比如他的电话本丢了，同时他又换了电话号，导致他跟所有人失去联系。

给出N个人之间的通信关系以及S和T，问最少几个人发生不好的事情可以导致S与T无法通信，并输出这些人。如果存在多组解，输出字典序最小的一组。

且假设不好的事情不会发生在S和T上，如果没有方法能使A和B失去联系，则输出”NO ANSWER!”

思路：首先需要把一个人i拆成两个点i和i\’。连边(i, i\’, 1)，那么发生不好的事情就表示这条边为割边。

然后对于i和j联通，连边(i\’, j, inf)和(j\’, i, inf)。

因为假设不好的事情不会发生在S和T上，所以把网络流的s设为S\’，把网络流的t设为T。

然后求一次最小割，就是答案，要注意的是如果在初始图中S和T直接联通，那么答案是”NO ANSWER!”。

要求输出字典序最小，假如一开始求出的最小割的值为x。然后可以从1到N枚举删除点，如果删除一个点之后最小割不变，那么这个点不在最小割中，把这个点恢复。

如果最小割变小了，那么更新最小割的值，输出这个点，然后不再把这个点恢复，直到输出了x个点。

  1 //#include <bits/stdc++.h>
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <cmath>
  6 #include <vector>
  7 #include <queue>
  8 using namespace std;
  9 struct Edge
 10 {
 11     int from, to, cap, flow;
 12     Edge(int f, int t, int c, int fl)
 13     {
 14         from = f; to = t; cap = c; flow = fl;
 15     }
 16 };
 17 #define maxn 410
 18 #define inf 0x3f3f3f3f
 19 vector <Edge> edges;
 20 vector <int> G[maxn];
 21 int n, m, s, t;
 22 int vis[maxn], cur[maxn], d[maxn];
 23 void AddEdge(int from, int to, int cap)
 24 {
 25     edges.push_back(Edge(from, to, cap, 0));
 26     edges.push_back(Edge(to, from, 0, 0));
 27     m = edges.size();
 28     G[from].push_back(m-2);
 29     G[to].push_back(m-1);
 30 }
 31 bool bfs()
 32 {
 33     memset(vis, 0, sizeof(vis));
 34     vis[s] = 1; d[s] = 0;
 35     queue <int> q;
 36     q.push(s);
 37     while(!q.empty())
 38     {
 39         int x = q.front(); q.pop();
 40         for(int i = 0; i < G[x].size(); i++)
 41         {
 42             Edge &e = edges[G[x][i]];
 43             if(!vis[e.to] && e.cap > e.flow)
 44             {
 45                 vis[e.to] = 1;
 46                 d[e.to] = d[x] + 1;
 47                 q.push(e.to);
 48             }
 49         }
 50     }
 51     return vis[t];
 52 }
 53 int dfs(int x, int a)
 54 {
 55     if(x == t || a == 0) return a;
 56     int flow = 0, f;
 57     for(int &i = cur[x]; i < G[x].size(); i++)
 58     {
 59         Edge &e = edges[G[x][i]];
 60         if(d[e.to] == d[x]+1 && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0)
 61         {
 62             e.flow += f;
 63             edges[G[x][i]^1].flow -= f;
 64             flow += f;
 65             a -= f;
 66             if(a == 0) break;
 67         }
 68     }
 69     return flow;
 70 }
 71 int maxflow()
 72 {
 73     int flow = 0;
 74     while(bfs())
 75     {
 76         memset(cur, 0, sizeof(cur));
 77         flow += dfs(s, inf);
 78     }
 79     return flow;
 80 }
 81 int N, S, T;
 82 int mp[maxn][maxn];
 83 int main() 
 84 {
 85     while(~scanf("%d%d%d", &N, &S, &T))
 86     {
 87         edges.clear();
 88         for(int i = 1; i <= 2*N; i++) G[i].clear();
 89         for(int i = 1; i <= N; i++)
 90         {
 91             for(int j = 1; j <= N; j++)
 92             {
 93                 int a; scanf("%d", &a);
 94                 mp[i][j] = a;
 95                 if(i == j) AddEdge(i, N+j, 1);
 96                 else if(i != j && a) AddEdge(N+i, j, inf);   
 97             }
 98         }
 99         s = S+N; t = T; n = 2*N; 
100         int ans = maxflow();
101         if(mp[S][T] == 1) { printf("NO ANSWER!\n"); continue;}
102         else printf("%d\n",  ans);
103         
104         int total = ans;
105         int cnt = 0;
106         for(int p = 1; p <= N; p++)
107         {
108             if(cnt == total) break;
109             else if(p == S || p == T) continue;
110             edges.clear();
111             for(int i = 1; i <= 2*N; i++) G[i].clear();
112             for(int i = 1; i <= N; i++)
113             {
114                 for(int j = 1; j <= N; j++)
115                 {
116                     if(i == p || j == p) continue;
117                     if(i == j) AddEdge(i, N+j, 1);        
118                     else if(i != j && mp[i][j]) AddEdge(N+i, j, inf);
119                 }
120             }
121             int flow = maxflow();
122             if(flow < ans)
123             {
124                 if(cnt == 0) printf("%d", p);
125                 else printf(" %d", p);
126                 if(cnt == total-1) printf("\n");
127                 cnt++; ans = flow;
128                 for(int i = 1; i <= N; i++) mp[p][i] = mp[i][p] = 0;
129             }
130         }
131     }
132     return 0;
133 }

 

版权声明：本文为titicia原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/titicia/p/5277181.html