2017团体程序设计天梯赛大区赛 L3-3 球队“食物链”

思路：
状压dp。
实现：
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int N = 20;
 7 
 8 char a[N][N];
 9 int n, s, t, ans[N + 5], mp[N][N];
10 int dp[(1 << N) + 5][N];
11 int path[(1 << N) + 5][N];
12 bool ok = false;
13 
14 int dfs(int S, int now)
15 {
16     if (dp[S][now] != -1)
17         return dp[S][now];
18     if (S == (1 << n) - 1)
19     {
20         if (mp[now][s])
21         {
22             t = now;
23             return ok = 1;
24         }
25         return 0;
26     }
27     for (int i = 0; i < n; i++)
28     {
29         if (ok)
30             continue;
31         if (!(S & (1 << i)) && mp[now][i])
32         {
33             int res = dfs(S | (1 << i), i);
34             path[S][now] = i;
35             if (res)
36                 return dp[S][now] = 1;
37         }
38     }
39     return dp[S][now] = (ok ? -1 : 0);
40 }
41 
42 void getPath()
43 {
44     int p = 1 << s;
45     ans[0] = s;
46     int i = 1;
47     for (int j = 0; j < n; j++)
48     {
49         ans[i++] = s = path[p][s];
50         p |= (1 << s);
51     }
52 }
53 
54 int main()
55 {
56     cin >> n;
57     for (int i = 0; i < n; i++)
58     {
59         for (int j = 0; j < n; j++)
60         {
61             cin >> a[i][j];
62             if (a[i][j] == 'W')
63                 mp[i][j] = 1;
64             else if (a[i][j] == 'L')
65                 mp[j][i] = 1;
66         }
67     }
68     memset(dp, -1, sizeof(dp));
69     for (int i = 0; i < n; i++)
70     {
71         s = i;
72         dfs(1 << i, i);
73         if (ok)
74             break;
75     }
76     if (!ok)
77     {
78         cout << "No Solution" << endl;
79     }
80     else
81     {
82         getPath();
83         for (int i = 0; i < n; i++)
84         {
85             cout << ans[i] + 1;
86             if (i != n - 1)
87                 cout << " ";
88         }
89         puts("");
90     }
91     return 0;
92 }