题意

n 名选手进行淘汰赛，R[i][j] = 1 表示 i 能胜过 j。要求通过安排淘汰赛使得，m 选手获得最终胜利，问使得比赛数最少的方案数。

分析

设 f(i, h, S) 表示 i 选手获胜 比赛 h 场 参赛选手集合为 S 的比赛方案有多少种。

那么状态转移就是 \(f(i, h, S) = \sum{f(i, h - 1, S') * f(j, h - 1, S - S')}\)，满足 i 能胜过 j，\(i \in S'\)，\(j \in {S - S'}\)。

code

#include
    
     using namespace std;const int MAXN = 1 << 16;int n, m;int bit1[MAXN]; // 二进制数中有多少个 1int dp[20][10][MAXN];vector
     
       G[20];int dfs(int u, int h, int bits) {    if(bit1[bits] == 1) return 1;    if((1 << h) < bit1[bits]) return 0;    if(dp[u][h][bits] != -1) return dp[u][h][bits];    else dp[u][h][bits] = 0;    int& res = dp[u][h][bits];    for(int i = bits & (bits - 1); i; i = bits & (i - 1)) { // 枚举 bits 里的 1 选或不选的情况        if((i >> u) & 1) {            int j = bits ^ i;            for(int k = 0; k < G[u].size(); k++) {                int v = G[u][k];                if((j >> v) & 1) {                    res += dfs(u, h - 1, i) * dfs(v, h - 1, j);                }            }        }    }    return res;}int main() {    for(int i = 0; i < MAXN; i++) {        bit1[i] = bit1[i >> 1] + (i & 1);    }    while(cin >> n >> m && (n + m)) {        memset(dp, -1, sizeof dp);        for(int i = 0; i < n; i++) G[i].clear();        for(int i = 0; i < n; i++) {            for(int j = 0; j < n; j++) {                int x;                cin >> x;                if(x) G[i].push_back(j);            }        }        int h = ceil(log(n) / log(2));        cout << dfs(m - 1, h, (1 << n) - 1) << endl;    }    return 0;}