度度熊国王率领着喵哈哈族的勇士，准备进攻哗啦啦族。
哗啦啦族是一个强悍的民族，里面有充满智慧的谋士，拥有无穷力量的战士。
所以这一场战争，将会十分艰难。
为了更好的进攻哗啦啦族，度度熊决定首先应该从内部瓦解哗啦啦族。
第一步就是应该使得哗啦啦族内部不能同心齐力，需要内部有间隙。
哗啦啦族一共有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 1 3 最小割定理，堆优化，稀疏图用邻接表。 /stoer-wagner算法 #include<stdio.h> #include<string.h> #include<queue> #include<algorithm> #include<iostream> using namespace std; int n; int head[3010]; int v[3010]; int maps[3010][3010]; struct node { int to; int c; int next; int pre; int v; } edge[200010]; struct ver { int e_n; int x; int dis; bool operator < (const ver& t) const { return dis<t.dis; } }; int prime(int &t,int temp_n,int &edge_num) { int vis[3010],dis[3010],v_j,res; priority_queue<ver> q; for(int i = 0; i<n; i++) { dis[i] = 0; vis[i] = v[i]; } vis[0] = 1; for(int i = head[0]; i!= -1; i = edge[i].next) { v_j = edge[i].to; if(vis[v_j] == 0) { dis[v_j] += edge[i].c; q.push(ver{i,v_j,dis[v_j]});//x-y-c } } int temp_j = 0; ver t_ver = q.top(); for(int i = 1; i<temp_n; i++) { do { t_ver = q.top(); q.pop(); } while(vis[t_ver.x] != 0); temp_j = t_ver.x; vis[temp_j] = 1; if(i == temp_n-1) { t = temp_j; edge_num = t_ver.e_n; res = t_ver.dis; } for(int j = head[temp_j]; j!=-1; j = edge[j].next) { v_j = edge[j].to; if(!vis[v_j]) { dis[v_j] += edge[j].c; q.push(ver{j,v_j,dis[v_j]}); } } } return res; } int stoer_wagner() { queue<int>q1; memset(v,0,sizeof(v)); int min_cut = 0x7fffffff,t,e_num,temp_n = n,res,pre,v_pre; for(int i = 1; i<n; i++) { res = prime(t,temp_n - i + 1,e_num); v[t] =1; min_cut = min(res,min_cut); pre = edge[e_num].pre; v_pre = edge[pre].to; for(int j = head[v_pre]; j!=-1; j = edge[j].next) { for(int k = head[t]; k !=-1; k = edge[k].next) { if(edge[j].to == edge[k].to) //same edge { //puts("s+for2"); edge[j].c += edge[k].c; edge[edge[j].pre].c = edge[j].c; edge[k].v = 1; } } } for (int k = head[t]; k!=-1; k = edge[k].next) { if(edge[k].v == 0&&edge[k].to != v_pre) { q1.push(k); edge[edge[k].pre].to = v_pre; } } while(!q1.empty()) { int tx = q1.front(); q1.pop(); edge[tx].next = head[v_pre]; head[v_pre] = tx; } } return min_cut; } void init1() { for(int i = 0; i<n; i++) { head[i] = -1 ; } } bool init2() { int u=0,v=0, c=0, k = 0; int pre1=0,pre2=0; for(int i = 0; i<n; i++) { for(int j = i+1; j<n; j++) { if(maps[i][j]) { u = i; v = j; c = maps[i][j]; edge[k].next = head[u]; edge[k].to = v; edge[k].c = c; edge[k].v = 0; head[u] = k; pre1 = k; k++; edge[k].next = head[v]; edge[k].to = u; edge[k].c = c; edge[k].v = 0; head[v] = k; pre2 = k; k++; edge[pre1].pre = pre2; edge[pre2].pre = pre1; } } } if(k/2 < n-1)return false; return true; } bool col() { queue<int> q2; int vv[3010]; memset(vv,0,sizeof(vv)); int s = 0; int ii = 0; q2.push(s); vv[s] = 1; while(!q2.empty()) { s = q2.front(); q2.pop(); for(int i = head[s]; i!=-1; i = edge[i].next) { ii = edge[i].to; if(vv[ii] == 0) { q2.push(ii); vv[ii] = 1; } } } for(int i= 0; i<n; i++) { if(vv[i] == 0)return false; } return true; } int main() { int ms,u,v,c; while(~scanf("%d%d",&n,&ms)) { memset(maps,0,sizeof(maps)); init1(); for(int i = 0; i<ms; i++) { scanf("%d%d%d",&u,&v,&c); u -= 1; v -= 1; maps[v][u] = maps[u][v] += c; } if(init2()==false||col() == false) { puts("0"); } else cout<<stoer_wagner()<<endl; } }