加载中...

POJ 2531 - Network Saboteur

算法

原创

发布日期: 2011-01-12

更新日期: 2024-12-30

文章字数: 759

阅读时长: 3 分

阅读次数:

POJ 2531 - Network Saboteur
Time: 2000MS
Memory: 65536K
难度: 初级
分类: 随机化算法

问题描述

把一个完全图分成两部分，使得连接这两部分边的权和最大。

解题思路

图论的无向完全图的最大割问题 （做网络最大流的时候同学们应该看过最小割，如果不懂最大割可以百度谷歌。）

可以用 随机化算法 Random Algorithm 去做

一开始我没读懂题，以为是求最大权。。。傻呼呼的用最了最小生成树的算法去做。

一直RERERE。。。还以为是数组开得不够大。。。悲剧啊。。。

虽然是图论，但不懂得为什么人家要把这题归类到搜索题去，用搜索我完全没思路去做。。。。

不多说，详细思路看我的程序，解释非常详尽

AC 源码

//Memory Time
//188K   375MS 

#include<iostream>
using namespace std;

const int TimeLimit=2000;  //本题时间限制为2000ms

int main(int i,int j)
{
    int n;
    while(cin>>n)
    {
        /*Input*/

        int w[30][30]={0};
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                cin>>w[i][j];
                w[j][i]=w[i][j];  //双向完全图
            }

        /*Random Algorithm*/

        bool subset[30]={false};    //A集:true  B集:false
        int time=TimeLimit*100;  //使随机次数尽可能大，随机结果尽可能接近最优解
        long max_w=0;   //最大割的权值之和
        long sum=0;  //当前边割集权和

        while(time--)
        {
            int x=rand()%n+1;  //生成随机数 x，对应于总集合的某个结点x
                               //注意由于使用的结点序号为1~n，对应了数组下标，下标为0的数组元素没有使用
                               //那么这里必须+1，因为若rand()=n，那么再对n取模结果就为0
                               //这时就会导致使用了不存在的 [0]结点，本应使用的 [n]结点就被丢弃了

            subset[x]=!subset[x];  //改变x所在的集合位置

            for(int i=1;i<=n;i++)   //由于是完全图，所以每个顶点i都与x相关联，因此要全部枚举
            {
                if(subset[i]!=subset[x])   //结点i 和 x分别在两个集合内
                    sum+=w[i][x];   //就是说因为x所在集合的改变，使得割边的个数增加
                                    //割集的原权值 要加上 当前新加入的割边(i,x)的权值

                if(i!=x && subset[i]==subset[x])  //结点i 和 x分别在相同的集合内，但他们不是同一元素
                    sum-=w[i][x];   //就是说因为x所在集合的改变，使得割边的个数减少
                                    //割集的原权值 要减去 当前失去的割边(i,x)的权值
            }

            if(max_w < sum)
                max_w = sum;
        }

        cout<<max_w<<endl;
    }
    return 0;
}