
ZOJ Problem Set  2753
Given an undirected graph, in which two vertexes can be connected by multiple edges, what is the mincut of the graph? i.e. how many edges must be removed at least to partition the graph into two disconnected subgraphes? Input Input contains multiple test cases. Each test case starts with two integers N and M (2<=N<=500, 0<=M<=N*(N1)/2) in one line, where N is the number of vertexes. Following are M lines, each line contains M integers A, B and C (0<=A,B<N, A<>B, C>0), meaning that there C edges connecting vertexes A and B. Output There is only one line for each test case, which is the mincut of the graph. If the graph is disconnected, print 0. Sample Input 3 3 0 1 1 1 2 1 2 0 1 4 3 0 1 1 1 2 1 2 3 1 8 14 0 1 1 0 2 1 0 3 1 1 2 1 1 3 1 2 3 1 4 5 1 4 6 1 4 7 1 5 6 1 5 7 1 6 7 1 4 0 1 7 3 1 Sample Output 2 1 2 Author: WANG, Ying Source: Baidu Star 2006 SemiFinal 