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
这道题目我自己看出来是最小割的问题,而之前的题目有一道是最小割的

但是有一个不同,这道题是点的最小割,而不是常规的边的最小割

所以这就比较麻烦,需要我们把点转化成边

这就让我想起了之前的那个Fence Loops

我就是把所有的边表示的图转化成了点表示的图,我实在是不想再写那么恶心的算法了。

然后我就去NoCow上面看了一下,果然是有很赞的方法。

具体方法就是,把一个点变成两个点,然后在两个点之间加一条边,并且这条边的权值是1

这样的话,如果割这条边,就相当于去掉了这个点。

剩下的事情就是跟前面的那个Pollute Control差不多了

每次去掉一条边,然后用MaxFlow求一下最大流,如果得出的最大流==最大流-边的权值

那么就证明这条边是最小割。

就这样把所有的最小割找出来,然后就可以了

貌似数据很弱,不像上次的那个Pollute那道题目,还要考虑边的编号的问题的。