poj 2914&&hdu 3002 全局最小割Stoer-Wagner算法模板

#include<stdio.h>

#include<string.h>

#include<iostream>

#define inf 0x3fffffff

#define N 510

int  n,ma[N][N],combine[N];

int seach(int &s,int &t) {

  int vis[N],i,j,tm,maxx,w[N];

  memset(vis,0,sizeof(vis));

  memset(w,0,sizeof(w));

  tm=10000;

  for(i=0;i<n;i++) {

      maxx=-inf;

    for(j=0;j<n;j++)

        if(!vis[j]&&!combine[j]&&maxx<w[j]) {//找到最大值

            maxx=w[j];

            tm=j;

        }

        if(t==tm) {return w[t];}//最后t和tm相等

        vis[tm]=1;

        s=t;t=tm;

        for(j=0;j<n;j++)//

        if(!vis[j]&&!combine[j])

            w[j]+=ma[t][j];

  }

  return w[t];

}

int mincut() {

int   mi=inf,ans,i,s,t,j;

memset(combine,0,sizeof(combine));

for(i=0;i<n-1;i++) {//只需要找n-1次

    s=-1;t=-1;

    ans=seach(s,t);//找到t和t的前一个点s

    combine[t]=1;//移除

    if(ans<mi)mi=ans;

    for(j=0;j<n;j++) {//将t合并到s点

        ma[s][j]+=ma[t][j];

        ma[j][s]+=ma[j][t];

    }

}

return mi;

}

int main() {

     int m,i,j,k;

     while(scanf("%d%d",&n,&m)!=EOF) {

        memset(ma,0,sizeof(ma));

        while(m--) {

            scanf("%d%d%d",&i,&j,&k);

            ma[i][j]+=k;ma[j][i]+=k;

        }

        printf("%d\n",mincut());

     }

return 0;

}

巴特西

poj 2914&&hdu 3002 全局最小割Stoer-Wagner算法模板

最新文章

热门文章