Algorithm

USACO Section5.4 Telecowmunication (telecow)

Problem Summary

Given a undirected graph, a source and a sink, find the minimal number of vertices needed to be taken away so that the source and sink are disconnected.

Solution

This problem ask for the minimum cut of vertices. We can easily transform it to the classic minimum cut problem with a few steps:

  1. Spliting every vertex into two vertices, one in-point and one out-point.
  2. Add an edge with 1 capacity between each pair of in-point and out-point to the new graph.
  3. For every edge (i,j) in the original graph, add an edge with infinite capacity between the in-point of i and the out-point of j, and an edge with infinite capacity between the out-point of i and the in-point of j.

Then we just need to find the min cut of the new graph,i.e. the max flow. This can be easily done with Dinic’s algorithm.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
#include <fstream>
#include <cstring>
#include <climits>
using namespace std;
const int maxn = 202;
int n,m,tot;
int g[maxn][maxn],backup[maxn][maxn],rest[maxn];
int head,tail,qu[maxn],level[maxn];
int ans,cut[maxn];
bool connected()
{
	memset(level,0,sizeof(level));
	qu[0]=0;
	level[0]=1;
	head=0; tail=1;
	int cur;
	while(head<tail)
	{
		cur=qu[head];
		head++;
		for(int i=1;i<=tot;i++)
			if(g[cur][i]>0 && level[i]==0)
			{
				level[i]=level[cur]+1;
				qu[tail]=i;
				tail++;
			}
	}
	return (level[tot]!=0);
}
int flow(int cur,int max)
{
	if(cur==tot) return max;
	for(int i=1;i<=tot;i++)
		if(g[cur][i]>0 && level[i]==level[cur]+1)
		{
			int new_flow=g[cur][i]<max ? g[cur][i]:max;
			int tmp=flow(i,new_flow);
			if(tmp>0)
			{
				g[cur][i]-=tmp;
				g[i][cur]+=tmp;
				return tmp;
			}
		}
	return 0;
}
int dinic()
{
	int res=0;
	while(connected())
		res+=flow(0,INT_MAX);
	return res;
}
int main()
{
	fstream fin("telecow.in",ios::in);
	fstream fout("telecow.out",ios::out);
	int a,b,st,en;
	fin>>n>>m>>st>>en;
	tot=(n<<1)+1;
	for(int i=0;i<m;i++)
	{
		fin>>a>>b;
		g[a+n][b]=g[b+n][a]=INT_MAX;
	}
	fin.close();
	g[0][st]=g[en+n][tot]=INT_MAX;
	for(int i=1;i<=n;i++)
		if(i!=st && i!=en)
			g[i][i+n]=1;
		else
			g[i][i+n]=INT_MAX;
	for(int i=1;i<=tot;i++)
		for(int j=1;j<=tot;j++)
			backup[i][j]=g[i][j];
	ans=dinic();
	
	if(ans==0)
	{
		fout<<0<<endl<<endl;
		fout.close();
		return 0;
	}
	
	fout<<ans<<endl;
	for(int i=1;i<=n;i++)
		rest[i]=g[i][i+n];
	for(int i=1;i<=n;i++)
		if(i!=st && i!=en && rest[i]==0)
		{
			for(int j=1;j<=tot;j++)
				for(int k=1;k<=tot;k++)
					g[j][k]=backup[j][k];
			g[i][i+n]=0;
			int sum=dinic();
			
			if(sum==ans-1)
			{
				cut[0]++;
				cut[cut[0]]=i;
				backup[i][i+n]=0;
				ans--;
				if(ans==0) break;
			}
		}
	for(int i=1;i<=cut[0];i++)
		if(i==1)
			fout<<cut[i];
		else
			fout<<" "<<cut[i];
	fout<<endl;
	fout.close();
	return 0;
}