?
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元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
