深圳福田住房和建设局网站,柴沟堡做网站,郑州网站推广策,企业网站百度指数多少算竞争大prim算法不仅仅可以求最小生成树#xff0c;也可以求“最大生成树”。最小割集Stoer-Wagner算法就是典型的应用实例。 求解最小割集普遍采用Stoer-Wagner算法#xff0c;不提供此算法证明和代码#xff0c;只提供算法思路#xff1a; 1.minMAXINT#xff0c;固定一个顶点P… prim算法不仅仅可以求最小生成树也可以求“最大生成树”。最小割集Stoer-Wagner算法就是典型的应用实例。 求解最小割集普遍采用Stoer-Wagner算法不提供此算法证明和代码只提供算法思路 1.minMAXINT固定一个顶点P 2.从点P用“类似”prim的s算法扩展出“最大生成树”记录最后扩展的顶点和最后扩展的边 3.计算最后扩展到的顶点的切割值即与此顶点相连的所有边权和若比min小更新min 4.合并最后扩展的那条边的两个端点为一个顶点当然他们的边也要合并这个好理解吧 5.转到2合并N-1次后结束 6.min即为所求输出min // 2914.cpp : 定义控制台应用程序的入口点。//#include stdafx.h#includestdio.h#includestring.h#define NN 504#define INF 130int vis[NN];int wet[NN];int combine[NN];int map[NN][NN];int S,T,minCut,N;void Search(){int i,j,Max,tmp; memset(vis,0,sizeof(vis)); memset(wet,0,sizeof(wet)); ST-1;for(i0;iN;i) { Max-INF;for(j0;jN;j) {if(!combine[j]!vis[j]wet[j]Max) { tmpj; Maxwet[j]; } }if(Ttmp)return; ST;Ttmp; minCutMax; vis[tmp]1;for(j0;jN;j) {if(!combine[j]!vis[j]) { wet[j]map[tmp][j]; } } }}int Stoer_Wagner(){int i,j; memset(combine,0,sizeof(combine));int ansINF;for(i0;iN-1;i) { Search();if(minCutans) ansminCut;if(ans0)return 0; combine[T]1;for(j0;jN;j) {if(!combine[j]) { map[S][j]map[T][j]; map[j][S]map[j][T]; } } }return ans;}int main(){int a,b,c,M;while(scanf(%d%d,N,M)!EOF) { memset(map,0,sizeof(map));while(M--) { scanf(%d%d%d,a,b,c); map[a][b]c; map[b][a]c; } printf(%d\n,Stoer_Wagner()); } getchar();return 0;} 转载于:https://www.cnblogs.com/zhanglanyun/archive/2011/06/05/2073209.html
