度度熊国王率领着喵哈哈族的勇士，准备进攻哗啦啦族。
哗啦啦族是一个强悍的民族，里面有充满智慧的谋士，拥有无穷力量的战士。
所以这一场战争，将会十分艰难。
为了更好的进攻哗啦啦族，度度熊决定首先应该从内部瓦解哗啦啦族。
第一步就是应该使得哗啦啦族内部不能同心齐力，需要内部有间隙。
哗啦啦族一共有n个将领，他们一共有m个强关系，摧毁每一个强关系都需要一定的代价。
现在度度熊命令你需要摧毁一些强关系，使得内部的将领，不能通过这些强关系，连成一个完整的连通块，以保证战争的顺利进行。
请问最少应该付出多少的代价。
Input本题包含若干组测试数据。
第一行两个整数n，m，表示有n个将领，m个关系。
接下来m行，每行三个整数u,v,w。表示u将领和v将领之间存在一个强关系，摧毁这个强关系需要代价w
数据范围：
2<=n<=3000
1<=m<=100000
1<=u,v<=n
1<=w<=1000
Output对于每组测试数据，输出最小需要的代价。
Sample Input 2 1 1 2 1 3 3 1 2 5 1 2 4 2 3 3 Sample Output Copy 1 3 最小割思想 代码如下： #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <iostream> #define min(a,b) ((a)<(b)?(a):(b)) using namespace std; const int MAX = 2000; const int INF = 1<<30; int map[MAX][MAX]; int v[MAX], dis[MAX]; bool vis[MAX]; int Stoer_Wagner(int n){ int i, j, res = INF; for(i = 0; i < n; i ++) v[i] = i; while(n > 1){ int k = 1, pre = 0; for(i = 1; i < n; i ++){ dis[v[i]] = map[v[0]][v[i]]; if(dis[v[i]] > dis[v[k]]) k = i; } memset(vis, 0, sizeof(vis)); vis[v[0]] = true; for(i = 1; i < n; i ++){ if(i == n-1){ res = min(res, dis[v[k]]); for(j = 0; j < n; j ++){ map[v[pre]][v[j]] += map[v[j]][v[k]]; map[v[j]][v[pre]] += map[v[j]][v[k]]; } v[k] = v[-- n]; } vis[v[k]] = true; pre = k; k = -1; for(j = 1; j < n; j ++) if(!vis[v[j]]){ dis[v[j]] += map[v[pre]][v[j]]; if(k == -1 || dis[v[k]] < dis[v[j]]) k = j; } } } return res; } int main(){ int n, m, u, v, w; while(scanf("%d%d", &n, &m) != EOF){ memset(map, 0, sizeof(map)); while(m --){ scanf("%d%d%d", &u, &v, &w); map[u-1][v-1] += w; map[v-1][u-1] += w; } printf("%d\n", Stoer_Wagner(n)); } return 0; } /* 2 1 0 1 1 3 3 0 1 5 0 1 4 1 2 3 */ 但是这个代码超时，哎~