长春赛区2012 USACO ORZ 1011题 (网络赛)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4277
DFS枚举，固定一条边即可。。。这样也能过，相当拙劣。。
//STATUS:C++_AC_890MS_4732KB #include<stdio.h>#include<stdlib.h>#include<string.h>#include<vector>#include<queue>#include<math.h>#include<map>#include<set>using namespace std;#define LL __int64#define pii pair<int,int>const int MAX=20,INF=200000000;const double esp=1e-6;int min(int x,int y){return x<y?x:y;};int max(int x,int y){return x>y?x:y;};void DFS(int cur);int ok(int a,int b,int c);int num[MAX],A[MAX],vis[4],x[3];int T,n;set<pii> S;int main(){//freopen("in.txt","r",stdin); int i; scanf("%d",&T); while(T--) {S.clear();x[0]=x[1]=x[2]=0; memset(vis,0,sizeof(vis)); scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&num[i]); A[0]=A[1]=0;x[0]=num[0]+num[1]; vis[0]=2; DFS(2); A[0]=0,A[1]=1;x[0]=num[0],x[1]=num[1]; vis[0]=vis[1]=1; DFS(2); printf("%d\n",S.size()); } return 0;}void DFS(int cur){ int i; if(cur==n){ if(vis[0] && vis[1] && vis[2]){ if(ok(x[0],x[1],x[2])){int min1=min(x[0],min(x[1],x[2]));int max2=max(x[0],max(x[1],x[2]));S.insert(pii(min1,x[0]+x[1]+x[2]-min1-max2));} } return; } for(i=0;i<3;i++){ A[cur]=i;x[i]+=num[cur]; vis[i]++; DFS(cur+1);x[i]-=num[cur]; vis[i]--; } return;}int ok(int a,int b,int c){ return (a+b>c && a+c>b && b+c>a);}