USACO TeleCowmunication

这是一道和联通性有关的题目，USACO Chapter 4有介绍过解决这个题目的思路：

This is equivalent to the minimum node cut problem. The two given machines can be arbitrarily labeled the source and sink. The wires are bidirectional. Split each node into an in-node and an out-node, so that we limit the flow through any given machine to 1. Now, the maximum flow across this network is equivalent to the minimum node cut.（max-flow min-cut theorem, wikipedia）

To actually determine the cut, iterative remove the nodes until you find one which lowers the capacity of the network.

这个算法用到了“拆点”。在理解上述算法的前提下（后面说的一些概念是建立在“拆点”的图上的），仔细分析会发现，不“拆点”也可以，只需要修改一下最大流算法——找到增广路后直接删除路径上的点（除了始末两个），重复直到找不到增广路。这种算法的实质和上面的相同，复杂度也相同，不过实际运行会快一点。

得到了最大流后，以此尝试移除某个点，如果此时的最大流正好等于原来-1,那么这个点就是一个“关键点”。

最后，由于题目要输出排序最小的点集，于是进行一次DFS，然后移除点测试联通性即可。

上面说的相当混乱，看代码吧：

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004
005 int N,M,source,sink;
006 int cap[101][101] = {};
007 int tmp[101][101];
008 int queue[200];
009 int head,tail;
010 int exclude[101];
011 int oncut[101] = {};
012 int max;
013 int isdown[101] = {};
014
015 void enqueue(int node)
016 {
017     queue[tail ++] = node;
018 }
019
020 int dequeue()
021 {
022     return queue[head ++];
023 }
024
025 void init()
026 {
027     int a,b;
028     scanf("%d%d%d%d\n",&N,&M,&source,&sink);
029     while(M --)
030     {
031         scanf("%d%d\n",&a,&b);
032         cap[a][b] = cap[b][a] = 1;
033     }
034 }
035
036 int getmin(int a,int b)
037 {
038     if(a < b)    return a;
039     return b;
040 }
041
042 int prev[101];
043 int visit[101];
044 int flow[101];
045 int bfs()   //find augmenting path
046 {
047     int i,j;
048     head = tail = 0;
049     memset(flow,0,sizeof(flow));
050     memset(prev,0,sizeof(prev));
051     memset(visit,0,sizeof(visit));
052     enqueue(source);
053     visit[source] = 1;
054     flow[source] = 32000;
055     while(head < tail)
056     {
057         i = dequeue();
058         if(i == sink)
059             return flow[sink];
060         for(j = 1;j <= N;j ++)
061             if(tmp[i][j] > 0 && !visit[j] && !exclude[j])
062             {
063                 visit[j] = 1;
064                 flow[j] = getmin(flow[i],tmp[i][j]);
065                 prev[j] = i;
066                 enqueue(j);
067             }
068     }
069     return 0;
070 }
071
072 int solve()   //ford-fulkerson
073 {
074     int maxflow = 0;
075     int add,i;
076     memcpy(tmp,cap,sizeof(tmp));
077     while(1)
078     {
079         add = bfs();
080         if(add == 0)    break;
081         maxflow += add;
082         for(i = prev[sink];i != source;i = prev[i])   //exclude nodes on path
083             exclude[i] = 1;
084     }
085     return maxflow;
086 }
087
088 int reachable()   //whether source and sink are connected
089 {
090     int i,j;
091     head = tail = 0;
092     memset(visit,0,sizeof(visit));
093     enqueue(source);
094     visit[source] = 1;
095     while(head < tail)
096     {
097         i = dequeue();
098         if(i == sink)    return 1;
099         for(j = 1;j <= N;j ++)
100             if(cap[i][j] && !visit[j] && !isdown[j])
101             {
102                 visit[j] = 1;
103                 enqueue(j);
104             }
105     }
106     return 0;
107 }
108
109 void dfs(int node,int tot)
110 {
111     if(tot == max)
112     {
113         if(!reachable())
114         {
115             int i;
116             int flag = 1;
117             for(i = 1;i <= N;i ++)
118                 if(isdown[i])
119                 {
120                     if(flag)
121                     {
122                         flag = 0;
123                         printf("%d",i);
124                     }
125                     else
126                         printf(" %d",i);
127                 }
128             printf("\n");
129             exit(0);
130         }
131         return;
132     }
133     if(node > N)    return;
134     if(oncut[node])
135     {
136         isdown[node] = 1;
137         dfs(node + 1,tot + 1);
138         isdown[node] = 0;
139     }
140     dfs(node + 1,tot);
141 }
142
143 int main()
144 {
145     int i;
146     freopen("telecow.in","r",stdin);
147     freopen("telecow.out","w",stdout);
148     init();
149     max = solve();
150     printf("%d\n",max);
151     for(i = 1;i <= N;i ++) //find all "critical nodes"
152     {
153         if(i == source || i == sink)    continue;
154         memset(exclude,0,sizeof(exclude));
155         exclude[i] = 1;
156         if(solve() < max)
157             oncut[i] = 1;
158     }
159     dfs(1,0);
160     return 0;
161 }

同样附上“拆点”的代码，这个更方便理解：

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004 #define INFINITY 32000
005
006 int N,M,source,sink;
007 int adj[101][101] = {};
008 int cap[210][210] = {};
009 int tmp[210][210];
010 int queue[210];
011 int head,tail;
012 int oncut[210] = {};
013 int max;
014 int isdown[210] = {};
015
016 void enqueue(int node)
017 {
018     queue[tail ++] = node;
019 }
020
021 int dequeue()
022 {
023     return queue[head ++];
024 }
025
026 void init()
027 {
028     int a,b;
029     scanf("%d%d%d%d\n",&N,&M,&source,&sink);
030     int i;
031     for(i = 1;i <= N;i ++)   split nodes----one in, one out
032         cap[i][N + i] = cap[N + i][i] = 1;   //split nodes
033     while(M --)
034     {
035         scanf("%d%d\n",&a,&b);
036         adj[a][b] = adj[b][a] = 1;
037         cap[a + N][b] = INFINITY;
038         cap[b + N][a] = INFINITY;
039     }
040 }
041
042 int getmin(int a,int b)
043 {
044     if(a < b)    return a;
045     return b;
046 }
047
048 int prev[210];
049 int visit[210];
050 int flow[210];
051 int bfs()
052 {
053     int i,j;
054     head = tail = 0;
055     memset(flow,0,sizeof(flow));
056     memset(prev,0,sizeof(prev));
057     memset(visit,0,sizeof(visit));
058     enqueue(source);
059     visit[source] = 1;
060     flow[source] = INFINITY;
061     while(head < tail)
062     {
063         i = dequeue();
064         if(i == sink)
065             return flow[sink];
066         for(j = 1;j <= N * 2;j ++)
067             if(tmp[i][j] > 0 && !visit[j])
068             {
069                 visit[j] = 1;
070                 flow[j] = getmin(flow[i],tmp[i][j]);
071                 prev[j] = i;
072                 enqueue(j);
073             }
074     }
075     return 0;
076 }
077
078 int solve()   //standard ford-fulkerson
079 {
080     int maxflow = 0;
081     int add,i;
082     memcpy(tmp,cap,sizeof(tmp));
083     while(1)
084     {
085         add = bfs();
086         if(add == 0)    break;
087         maxflow += add;
088         for(i = sink;i != source + N;i = prev[i])
089         {
090             tmp[prev[i]][i] -= add;
091             tmp[i][prev[i]] += add;
092         }
093     }
094     return maxflow;
095 }
096
097 int reachable()
098 {
099     int i,j;
100     head = tail = 0;
101     memset(visit,0,sizeof(visit));
102     enqueue(source);
103     visit[source] = 1;
104     while(head < tail)
105     {
106         i = dequeue();
107         if(i == sink)    return 1;
108         for(j = 1;j <= N;j ++)
109         {
110             if(adj[i][j] && !visit[j] && !isdown[j])
111             {
112                 visit[j] = 1;
113                 enqueue(j);
114             }
115         }
116     }
117     return 0;
118 }
119
120 void dfs(int node,int tot)
121 {
122     if(tot == max)
123     {
124         if(!reachable())
125         {
126             int i;
127             int flag = 1;
128             for(i = 1;i <= N;i ++)
129                 if(isdown[i])
130                 {
131                     if(flag)
132                     {
133                         flag = 0;
134                         printf("%d",i);
135                     }
136                     else
137                         printf(" %d",i);
138                 }
139             printf("\n");
140             exit(0);
141         }
142         return;
143     }
144     if(node > N)    return;
145     if(oncut[node])
146     {
147         isdown[node] = 1;
148         dfs(node + 1,tot + 1);
149         isdown[node] = 0;
150     }
151     dfs(node + 1,tot);
152 }
153
154 int main()
155 {
156     int i;
157     freopen("telecow.in","r",stdin);
158     freopen("telecow.out","w",stdout);
159     init();
160     max = solve();
161     printf("%d\n",max);
162     for(i = 1;i <= N;i ++)
163     {
164         if(i == sink || i == source)    continue;
165         cap[i][i + N] = cap[i + N][i] = 0;
166         if(solve() < max)
167             oncut[i] = 1;
168         cap[i][i + N] = cap[i + N][i] = 1;
169     }
170     dfs(1,0);
171     return 0;
172 }