首页 > 代码库 > poj 2531 Network Saboteur
poj 2531 Network Saboteur
链接:poj 2531
题意:给定一个完全图,求将其分为两部分的边权值和最大
如:题中第一组样例:
3 0 50 30 50 0 40 30 40 0
将顶点分为两个集合A={2},B={1,3},sum=C21+C23=90为最大权值和
分析:dfs,先将顶点分为两个集合,再求权值和,取其最大值
可以用数组标记,为0的在一个集合,为1的在一个集合
#include<stdio.h> #include<string.h> int n,vis[25],ans,a[25][25]; void dfs(int pos,int sum) { int i,s; if(pos>n){ if(sum>ans) ans=sum; return ; } vis[pos]=1; s=0; for(i=1;i<pos;i++) if(!vis[i]) s+=a[pos][i]; dfs(pos+1,sum+s); vis[pos]=0; s=0; for(i=1;i<pos;i++) if(vis[i]) s+=a[pos][i]; dfs(pos+1,sum+s); } int main() { int i,j; while(scanf("%d",&n)!=EOF){ for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&a[i][j]); memset(vis,0,sizeof(vis)); ans=0; dfs(1,0); printf("%d\n",ans); } return 0; }
poj 2531 Network Saboteur
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。