Network Saboteur(Rand版)

poj2531:http://poj.org/problem?id=2531

题意:给你一个图,图中点之间会有边权,现在问题是把图分成两部分,使得两部分之间边权之和最大。
题解:随机算法

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int g[30][30];
int vis[30];
const int Timelimit=2000;//时间限制是2000
int main(){
   scanf("%d",&n);
   for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
      cin>>g[i][j];
   memset(vis,0,sizeof(vis));//0表示全部属于一个集合
   int Time=Timelimit*50;//随机次数,这个字数不能太少,如果改成*10就过不了
   int counts=0;//当前的最大值
   int maxn=0;//最大值
   while(Time--){
     int x=rand()%n+1;//产生随机数,注意,这里是1--n,所以要注意范围
       vis[x]=!vis[x];//改变当前的x所属的集合
       for(int i=1;i<=n;i++){
        if(vis[i]!=vis[x])//对于改变之后的x要统计新增加的边
            counts+=g[i][x];
        if(i!=x&&vis[i]==vis[x])//对于改变之后的x,之前与x不在一个集合点,这些点之间边现在要删除
            counts-=g[i][x];
       }
       if(counts>maxn)//更新最大值
        maxn=counts;
   }
   printf("%d\n",maxn);
}
View Code

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。