POJ 2531（搜索剪枝）

题目链接poj2531

题目大意

一个有n个节点的图（ n≤20 ），节点间距C给定，让你把这个图分为A、B两类节点使得 ∑Cij,(i∈A,j∈B) 最大，问这个最大值是多少。

分析

由于n很小只有20，可以直接枚举，复杂度是 220∗202 超时。需要剪枝。这道题的剪枝技巧是：

采用深度优先搜索的方法，对每一个节点都做判断是否应该移到另一组去，判断的依据是移过去和不移过去哪个得到的和值比较大。如果移过去后值变小了则不移过去并且剪掉这条支路。

这个剪枝策略的正确性证明还没想出来，以后再补。

#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<cstdlib> #include<queue> #include<stack> using namespace std; int n; int C[25][25]; int A[25]; int Ans; void Print() { for(int i=1;i<=n;i++) { cout<<A[i]; } cout<<endl; } void dfs(int x,int ans)//ans是不加x时的答案 { if(x==n+1) { //Print(); Ans=max(Ans,ans); return ; } int ans2=ans; dfs(x+1,ans); A[x]=1; for(int i=1;i<x;i++) if(A[i]==1)ans2-=C[x][i]; for(int i=1;i<=n;i++) if(A[i]==0)ans2+=C[x][i]; if(ans2>=ans){dfs(x+1,ans2);} A[x]=0; } 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",&C[i][j]); memset(A,0,sizeof(A)); dfs(1,0); cout<<Ans<<endl; } }