Network Saboteur

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

题意:给你一个图,图中点之间会有边权,现在问题是把图分成两部分,使得两部分之间边权之和最大。
题解:一开始比知道怎么办,想用搜索,但是20的范围,觉得范围有点大,所以没敢打,最后还是试了试结果竟然过了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[24],b[24];//记录图中的两部分
int num1,num2;
int counts,minn;
int vis[24];
int n;
int g[24][24];
void DFS(int x){//对于一个点来说,要么属于A部分,要么属于B部分,所以分两部分进行DFS
    if(x==n+1){//到了底部,就开始统计边权之和,然后比较,看看是否需要更新最大值。
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        num1=num2=0;
        for(int i=1;i<=n;i++){
            if(vis[i])
                a[++num1]=i;
            else
                b[++num2]=i;
        }
        counts=0;
       for(int i=1;i<=num1;i++)
       for(int j=1;j<=num2;j++){
          if(g[a[i]][b[j]])
            counts+=g[a[i]][b[j]];
       }
       if(counts>minn)
        minn=counts;
       return;
    }
    vis[x]=1;
    DFS(x+1);
    vis[x]=0;
    DFS(x+1);
}
int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
     cin>>g[i][j];
     minn=0;
    DFS(1);
    printf("%d\n",minn);
}
View Code

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