1 import java.io.*;
2 import java.util.*;
3 /*
4 ID:
5 LANG: JAVA
6 TASK:telecow
7 */
8 public class telecow {
9
10 public static final int WHITE = 0, GRAY = 1, BLACK = 2;
11 private int[][] flow, capacity, res_capacity;
12 private int[] parent, color, queue;
13 private int[] min_capacity;
14 private int size, source, sink, first, last;
15 private static int MAXN = 200;
16 int N,M;
17
18 private int maxFlow() // Edmonds-Karp algorithm with O(V3E) complexity
19 {
20 flow = new int[MAXN][MAXN];
21 res_capacity = new int[MAXN][MAXN];
22 parent = new int[MAXN];
23 min_capacity = new int[MAXN];
24 color = new int[MAXN];
25 queue = new int[MAXN];
26 int max_flow = 0;
27 for (int i = 0; i < size; i++)
28 for (int j = 0; j < size; j++)
29 res_capacity[i][j] = capacity[i][j];
30
31 while (BFS(source))
32 {
33 max_flow += min_capacity[sink];
34 int v = sink, u;
35 while (v != source)
36 {
37 u = parent[v];
38 flow[u][v] += min_capacity[sink];
39 flow[v][u] -= min_capacity[sink];
40 res_capacity[u][v] -= min_capacity[sink];
41 res_capacity[v][u] += min_capacity[sink];
42 v = u;
43 }
44 }
45 return max_flow;
46 }
47
48 private boolean BFS(int source) // Breadth First Search in O(V2)
49 {
50 for (int i = 0; i < size; i++) {
51 color[i] = WHITE;
52 min_capacity[i] = Integer.MAX_VALUE;
53 }
54
55 first = last = 0;
56 queue[last++] = source;
57 color[source] = GRAY;
58
59 while (first != last) // While "queue" not empty..
60 {
61 int v = queue[first++];
62 for (int u = 0; u < size; u++)
63 if (color[u] == WHITE && res_capacity[v][u] > 0)
64 {
65 min_capacity[u] = Math.min(min_capacity[v], res_capacity[v][u]);
66 parent[u] = v;
67 color[u] = GRAY;
68 if (u == sink) return true;
69 queue[last++] = u;
70 }
71 }
72 return false;
73 }
74
75 public void done() throws IOException {
76 BufferedReader f = new BufferedReader(new FileReader("telecow.in"));
77 PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("telecow.out")));
78 StringTokenizer st = new StringTokenizer(f.readLine());
79 N = Integer.parseInt(st.nextToken());
80 M = Integer.parseInt(st.nextToken());
81 source = Integer.parseInt(st.nextToken());
82 sink = Integer.parseInt(st.nextToken());
83 source--;
84 sink--;
85 int osource = source;
86 int osink = sink;
87 capacity = new int[N * 2][N * 2];
88
89 //init
90 for (int i = 0; i < N; i++)
91 capacity[i * 2][i * 2 + 1] = 1;
92
93 for (int i = 0; i < M; i++) {
94 st = new StringTokenizer(f.readLine());
95 int x = Integer.parseInt(st.nextToken());
96 int y = Integer.parseInt(st.nextToken());
97 x--;
98 y--;
99 capacity[x * 2 + 1][y * 2] = Integer.MAX_VALUE;
100 capacity[y * 2 + 1][x * 2] = Integer.MAX_VALUE;
101 }
102
103 for (int i = 0; i < 2 * N; i++) {
104 capacity[i][source * 2] = 0;
105 capacity[sink * 2 + 1][i] = 0;
106 }
107
108 int[] ans = new int[N + 1];
109
110 size = 2 * N;
111 source = source * 2 + 1;
112 sink = sink * 2;
113
114 int max = maxFlow();
115
116 int count = 0;
117 for (int i = 0; i < N; i++)
118 if (i != osource && i != osink) {
119 capacity[i * 2][i * 2 + 1] = 0;
120 int nowFlow = maxFlow();
121
122 if (max - nowFlow == count + 1)
123 ans[count++] = i;
124 else
125 capacity[i * 2][i * 2 + 1] = 1;
126 }
127
128 out.println(max);
129
130 for (int i = 0; i < count - 1; i++)
131 out.print(ans[i] + 1 + " ");
132 out.println(ans[count - 1] + 1);
133 out.close();
134
135 }
136
137 public static void main(String[] args) throws IOException {
138 telecow t = new telecow();
139 t.done();
140 System.exit(0);
141 }
142 }
143
這道題目我自己看出來是最小割的問題，而之前的題目有一道是最小割的
但是有一個(gè)不同，這道題是點(diǎn)的最小割，而不是常規(guī)的邊的最小割
所以這就比較麻煩，需要我們把點(diǎn)轉(zhuǎn)化成邊
這就讓我想起了之前的那個(gè)Fence Loops
我就是把所有的邊表示的圖轉(zhuǎn)化成了點(diǎn)表示的圖，我實(shí)在是不想再寫那么惡心的算法了。
然后我就去NoCow上面看了一下，果然是有很贊的方法。
具體方法就是，把一個(gè)點(diǎn)變成兩個(gè)點(diǎn)，然后在兩個(gè)點(diǎn)之間加一條邊，并且這條邊的權(quán)值是1
這樣的話，如果割這條邊，就相當(dāng)于去掉了這個(gè)點(diǎn)。
剩下的事情就是跟前面的那個(gè)Pollute Control差不多了
每次去掉一條邊，然后用MaxFlow求一下最大流，如果得出的最大流==最大流-邊的權(quán)值
那么就證明這條邊是最小割。
就這樣把所有的最小割找出來，然后就可以了
貌似數(shù)據(jù)很弱，不像上次的那個(gè)Pollute那道題目，還要考慮邊的編號(hào)的問題的。