题目大意：有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<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<cmath> 6 #include<math.h> 7 #include<algorithm> 8 #include<queue> 9 #include<set> 10 #include<bitset> 11 #include<map> 12 #include<vector> 13 #include<stdlib.h> 14 #include <stack> 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 long 20 #define eps 1e-10 21 #define MOD 1000000007 22 #define N 26 23 #define inf 1e12 24 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 }
poj 2531 Network Saboteur（经典dfs）
原文：http://www.cnblogs.com/UniqueColor/p/4960150.html
