poj2914无向图的最小割

http://blog.csdn.net/vsooda/article/details/7397449

//算法理论 http://www.cnblogs.com/ylfdrib/archive/2010/08/17/1801784.html

http://blog.csdn.net/i_love_home/article/details/9698791

以上是参考的博客

无向图的最小割我的理解就是先固定一个点，那么其余的点和他的关系就是是否在同一个集合内，既然要求最小割那么和他相连的最大的边最开始肯定是不切割的，而是将它看做和固定点同一个集合用于更新其余点的距离状态，而按照这样贪心的话只能保证局部最优而保证不了全局最优，因为可能与固定点连的最小的边的点可能和其余的点有一个非常大的连边,所以需n次循环弥补,相当于对每种可能的情况都进行了探索，有点贪心加枚举的感觉，向每一个有可能最优的情况探索，这样就大大减小了搜索的范围，然后又因为每次执行的步骤都一样，所以也被人叫迭代？。很有意思的一个算法。

#include<cstdio>

#include<cstring>

#include<algorithm>

const int N=;

using namespace std;

int mat[N][N];

int res;

void Mincut(int n)  //注意写的时候不要丢node

{

    int dist[N],node[N];

    bool vis[N];

    for(int i=; i<n; ++i) node[i]=i;

    while(n>)

    {

        int maxx=,prev=0;

        for(int i=; i<n; ++i)

        {

            dist[node[i]]=mat[node[]][node[i]];

            if(dist[node[i]]>dist[node[maxx]]) maxx=i;

        }

        memset(vis,,sizeof(vis));  //每次都要更新vis

        vis[node[]]=;

        for(int i=; i<n; ++i)

        {

            if(i==n-)

            {

                res=min(res,dist[node[maxx]]);

                for(int k=; k<n; ++k)

                    mat[node[k]][node[prev]]=(mat[node[prev]][node[k]]+=mat[node[maxx]][node[k]]);  //看清楚這

                node[maxx]=node[--n];

            }

            vis[node[maxx]]=;

            prev=maxx;

            maxx=-;

            for(int j=; j<n; ++j) if(!vis[node[j]])

            {

                dist[node[j]]+=mat[node[prev]][node[j]];  //更新的时候注意是prev,因为在更新的时候顺便把下一次循环的最大值搞了出来

                if(maxx==-||dist[node[j]]>dist[node[maxx]])  

                    maxx=j;

            }

        }

    }

    return ;

}

int main(){

   int n,m;

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

    res=;

    int u,v,w;

    memset(mat,,sizeof(mat));

    while(m--){

        scanf("%d%d%d",&u,&v,&w);

        mat[u][v]+=w;

        mat[v][u]+=w;

    }

    Mincut(n);

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

   }

}

巴特西

poj2914无向图的最小割

最新文章

热门文章