本文共 1386 字，大约阅读时间需要 4 分钟。
题目大意：有n个点，把这些点分别放到两个集合里，在两个集合的每个点之间都会有权值，求可能形成的最大权值。
思路：1、把这两个集合标记为0和1，先默认所有点都在集合0里。
2、依次枚举每个点id，把每个点都放到集合1里去，这个时候就要调整集合的权值了，原来和id都在集合0里的点，要把权值加上；而在集合1里的点，要把权值减去。
3、权值调整完毕后，和ans比较，如果比ans要大， 调整ans。
4、如果放到集合1中，调整节点后的权值比放在集合0中要大，那么就默认这个点在集合1中，继续枚举下面的点进行DFS。最终是可以把最有状态都枚举出来的。
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 using namespace std;16 #define PI acos(-1.0)17 #define max(a,b) (a) > (b) ? (a) : (b)18 #define min(a,b) (a) < (b) ? (a) : (b)19 #define ll long long20 #define eps 1e-1021 #define MOD 100000000722 #define N 2623 #define inf 1e1224 int n;25 int mp[N][N];26 int vis[N];27 int ans;28 void dfs(int id,int data){29 vis[id]=1;30 int tmp=data;31 for(int i=1;i<=n;i++){32 if(vis[i]==0){33 tmp+=mp[id][i];34 }else{35 tmp-=mp[id][i];36 }37 }38 ans=max(ans,tmp);39 for(int i=id+1;i<=n;i++){40 if(tmp>data){41 dfs(i,tmp);42 vis[i]=0;43 }44 }45 }46 int main()47 {48 while(scanf("%d",&n)==1){49 memset(vis,0,sizeof(vis));50 for(int i=1;i<=n;i++){51 for(int j=1;j<=n;j++){52 scanf("%d",&mp[i][j]);53 }54 }55 ans=-1;56 dfs(1,0);57 printf("%d\n",ans);58 }59 return 0;60 }
转载地址：http://nzaux.baihongyu.com/
