长春赛区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);}