?
http://acm.hdu.edu.cn/showproblem.php?pid=3691
Stoer-Wagner算法 不理解不理解呀
大體步驟是這樣子的
1,用類似Prim 的過程求得最后更新點 和倒數第二更新點
2,求最后更新點和其它點的割集
3,將最后一個點合并到倒數第二個更新點上
代碼:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int INF=0x7fffffff; const int N=305; int a[N][N]; int dist[N]; bool visited[N],dele[N]; int n,m,st; int nd1,nd2; void Prim() { memset(dist,0,sizeof(dist)); for(int i=1;i<=n;++i) { if(!dele[i]) { dist[i]=a[st][i]; } } nd1=nd2=st; memset(visited,false,sizeof(visited)); visited[st]=true; for(int w=1;w<n;++w) { int M=0,k=0; for(int i=1;i<=n;++i) { if(!dele[i]&&!visited[i]&&dist[i]>M) { M=dist[i];k=i; } } if(k==0) break; visited[k]=true; for(int i=1;i<=n;++i) { if(!dele[i]&&!visited[i]) { dist[i]+=a[k][i];//這里好奇怪 } } nd2=nd1;//最后更新點 和倒數第二更新點 nd1=k; } return; } int Findmin() { int sum=0; for(int i=1;i<=n;++i) { if(!dele[i]) { sum+=a[nd1][i];//最后更新點的割集 } } return sum; } void Removepoint() { dele[nd1]=true; for(int i=1;i<=n;++i) { if(!dele[i]&&i!=nd2) { a[i][nd2]+=a[i][nd1];//合并最后更新點 a[nd2][i]+=a[nd1][i]; } } } int main() { while(scanf("%d %d %d",&n,&m,&st)!=EOF) { if(!n&&!m&&!st) break; memset(a,0,sizeof(a)); while(m--) { int i,j,k; scanf("%d %d %d",&i,&j,&k); a[i][j]+=k;//重邊 a[j][i]+=k; } int ans=INF; memset(dele,false,sizeof(dele));//此點是否刪除 for(int w=1;w<n;++w) { Prim(); ans=min(ans,Findmin()); Removepoint(); } printf("%d\n",ans); } return 0; }
?
?
?
更多文章、技術交流、商務合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
