[cerc2012][Gym100624A]20181013

A

题意：n(n<=20)个国家，每个国家之间有一些债务关系，总体为负债的国家会破产，破产国家的债务关系全部消除。问哪些国家可能成为最后一个唯一存在的国家。

题解：

对于每一个状态，面对若干个负债国，哪个国家先破产会影响最后的结果。

考虑到n<=20，可以状压。f[s]表示状态为s（0表示未破产，1表示已破产）是否存在。

转移方程:if(!s&(1<<i) && i在s状态下已破产)  f[s+(1<<i)] | = f[s];

O(2^n * n^2)//很慢www谁有更好的方法请留言

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<queue>

 using namespace std;

 const int N=;

 int n,a[N][N],ok[N],f[];

 int main()

 {

     //freopen("a.in","r",stdin);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         for(int i=;i<n;i++)

             for(int j=;j<n;j++)

                 scanf("%d",&a[i][j]);

         memset(f,,sizeof(f));

         f[]=;

         for(int s=;s<(<<n);s++)

         {

             if(!f[s]) continue;

             for(int i=;i<n;i++)

             {

                 if(!(s&(<<i)))

                 {

                     int sum=;

                     for(int j=;j<n;j++)

                         if(!(s&(<<j))) sum-=a[i][j];

                     if(sum<) f[s|(<<i)]=;

                 }

             }

         }

         memset(ok,,sizeof(ok));

         int bk=,now=;

         for(int i=;i<n;i++)

             if(f[((<<n)-)-(<<i)]) ok[i]=,bk++;

         for(int i=;i<n;i++)

             if(ok[i])

             {

                 now++;

                 if(now<bk) printf("%d ",i+);

                 else printf("%d\n",i+);

             }

         if(!bk) printf("0\n");

     }

     return ;

 }