POJ 2531 Network Saboteur(DFS)

Description

Input

Output

Sample Input

3
0 50 30
50 0 40
30 40 0

Sample Output

90

题目大意： 有两个集合，求不同集合间的最大路径和。

#include<iostream>
#include<cstdio>
#include<string.h>
#include<string>
#include<cmath>
#include<queue>
#define mod 9901
#define LL long long
using namespace std;
int n;
int a[32][32];
bool vis[32];
int ans;
void dfs(int s,int sum)
{
     vis[s]=true;//利用标记数组划分出两个集合
    for(int i=1;i<=n;i++)
    {
        if(vis[i])//假设当前的数在集合中减去当前数到该集合的距离
            sum-=a[s][i];
        else
            sum+=a[s][i];//否则加上
    }
    ans=max(sum,ans);
    for(int i=s+1;i<=n;i++)//枚举下一个点再增加集合
    {
        vis[i]=true;
        dfs(i,sum);
        vis[i]=false;
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        memset(vis,false,sizeof(vis));
        dfs(1,0);
    printf("%d\n",ans);
    }
    return 0;
}