4525: [Cerc2012]Kingdoms

题意

　　n个国家，两两之间可能存在欠债或者被欠债的关系，一个国家破产：其支出大于收入。问一个国家能否坚持到最后。

思路

　　很有意思的一道题。

　　dp[s]表示在当前国家存在情况为s，1-存活，0-破产。那么起始为11111...。然后枚举一个国家，判断是否可以破产，转移。

　　最后，扫一遍所有只有1的情况。

代码

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<iostream>
 5  
 6 using namespace std;
 7 
 8 const int N = 30;
 9 int d[N][N],f[(1<<21)+10];
10 
11 inline int read() {
12     int x = 0,f = 1;char ch = getchar();
13     for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-1;
14     for (; isdigit(ch); ch=getchar()) x = x*10+ch-'0';
15     return x*f; 
16 }
17 
18 int main() {
19     int T = read();
20     while (T--) {
21         int n = read();
22         for (int i=1; i<=n; ++i) 
23             for (int j=1; j<=n; ++j) 
24                 d[i][j] = read();
25         int MaxS = (1<<n)-1; 
26         for (int i=0; i<=MaxS; ++i) f[i] = false;
27         f[MaxS] = true;
28         for (int s=MaxS; s>=1; --s) {
29             if (!f[s]) continue;
30             int ans = 0;
31             for (int i=1; i<=n; ++i) {
32                 if (!(s&(1<<(i-1)))) continue;
33                 int sum = 0 ;
34                 for (int j=1; j<=n; ++j) 
35                     if (s&(1<<(j-1))) sum += d[j][i]; //j欠i=>i可以获得的 
36                 if (sum < 0) f[s^(1<<(i-1))] = true; 
37             }
38         }
39         bool flag = true;
40         for (int i=1; i<=n; ++i) {
41             if (f[(1<<(i-1))]) {
42                 if (flag) printf("%d",i),flag = false;
43                 else printf(" %d",i);
44             }
45         }
46         if (flag) printf("0");
47         puts(""); 
48     }
49     return 0;
50 }