Network Saboteur(Rand版)
浏览数：25 /
时间：2015年06月09日
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); }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
