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); }