Given an undirected graph, in which two vertices can be connected by multiple edges, what is the size of the minimum cut of the graph? i.e. how many edges must be removed at least to disconnect the graph into two subgraphs?

Input contains multiple test cases. Each test case starts with two integers N and M (2 ≤ N ≤ 500, 0 ≤ M ≤ N × (N − 1) ⁄ 2) in one line, where N is the number of vertices. 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 vertices A and B.

There is only one line for each test case, which contains the size of the minimum cut 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

Source

        初次接触SW算法和全局最小割。之前一脸蒙圈，推荐这篇文章，讲的十分详细。点我点我！我是 “这篇文章“！ 

        绝对不是因为百度之星资格赛第二题把我气到了才奋发学习的！！！

        但是还是很想不通为什么POJ的大神们1s、 2s 就Ac了啊！！渣渣程序跑6s……

#include<cstdio>
#include<cstring>
#define min(a, b) (a < b ? a : b)
using namespace std;
const int maxn = 505;
int map[maxn][maxn];
int wg[maxn];
bool vis[maxn], del[maxn];
int m, n, pos, last, inset;

void SW() {
	memset(wg, 0, sizeof(int) * (n + 3));
	memset(vis, 0, sizeof(bool) * (n + 3));
	pos = last = 0;
	for(register int i = 1; i <= n - inset; ++i) {
		int mx = -1;
		last = pos;
		for(register int j = 1; j <= n; ++j) 
			if(wg[j] > mx && !del[j] && !vis[j]) mx = wg[j], pos = j;
		vis[pos] = 1;
		for(register int j = 1; j <= n; ++j)
			if(!vis[j] && !del[j]) wg[j] += map[pos][j];
	}
}

int MinCut() {
	int ans = 0x3f3f3f3f;
	for(register int i = 1; i < n; ++i) {
		SW();
		ans = min(ans, wg[pos]);
		if(ans == 0) return 0;
		for(register int i = 1; i <= n; ++i) 
			if(map[i][pos] && i != pos && i != last) {
				map[i][last] += map[i][pos], map[last][i] = map[i][last];
				map[pos][i] = map[i][pos] = 0;
			}
		del[pos] = 1;
		++inset;
	}
	return ans;
}

int main() {
	while(~scanf("%d%d", &n, &m)) {
		int u, v, w;
		inset = 0, pos = last = 0;
		for(register int i = 1; i <= n; ++i)
			for(register int j = 1; j <= n; ++j)
				map[i][j] = 0;
		memset(del, 0, sizeof(bool) * (n + 3));
		for(register int i = 1; i <= m; ++i) {
			scanf("%d%d%d", &u, &v, &w);
			map[u+1][v+1] += w;
			map[v+1][u+1] += w;
		}
		printf("%d\n", MinCut());
	}
	return 0;
}