/*代码抄袭来源: 一定要自己敲键盘抄一遍~~求解最小割集普遍采用Stoer-Wagner算法：1.min=MAXINT，固定一个顶点P2.从点P用类似prim的s算法扩展出“最大生成树”，记录最后扩展的顶点和最后扩展的边3.计算最后扩展到的顶点的切割值（即与此顶点相连的所有边权和），若比min小更新min4.合并最后扩展的那条边的两个端点为一个顶点（当然他们的边也要合并，，这个好理解吧？）5.转到2，合并N-1次后结束6.min即为所求，输出minprim本身复杂度是O(n^2)，合并n-1次，算法复杂度即为O(n^3)如果在prim中加堆优化，复杂度会降为O((n^2)logn)*/#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int NN=505;const int INF=0x3fffffff;int n,m,g[NN][NN],node[NN],dist[NN];bool used[NN];int mincut(){int maxj,pre,ret=INF;for (int i=0; i<n; i++) node[i]=i;while (n>1){memset(used,0,sizeof(used));used[node[0]]=1;maxj=1;//记录’最远’的结点for (int i=1; i<n; i++){dist[node[i]]=g[node[0]][node[i]]; //固定定点P为node[0],这里初始化distif (dist[node[i]]>dist[node[maxj]]) maxj=i;}pre=0;for (int i=1; i<n; i++){if (i==n-1)//生成树的最后一条边{ret=min(ret,dist[node[maxj]]); //更新最小割for (int k=0; k<n; k++)//合并pre和maxj两点{g[node[k]][node[pre]]+=g[node[k]][node[maxj]];g[node[pre]][node[k]]=g[node[k]][node[pre]];}node[maxj]=node[–n];//删掉maxj结点}used[node[maxj]]=1;pre=maxj;maxj=-1;for (int j=1; j<n; j++)if (!used[node[j]]){dist[node[j]]+=g[node[pre]][node[j]]; //更新到树的和距离if (maxj==-1 || dist[node[maxj]]<dist[node[j]]) maxj=j;}}}return ret;}int main(){while (scanf("%d%d",&n,&m)!=-1){memset(g,0,sizeof(g));for (int i=1; i<=m; i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);g[a][b]+=c;g[b][a]+=c;}printf("%d\n",mincut());}return 0;}
要纠正别人之前，先反省自己有没有犯错
