题目地址：UVa：UVa Online Judge

题目描述

原题面参见UVa/vjudge。
给定一个点数为n的竞赛图，求图的最小支配集。

题解

竞赛图是指任意两点只有一条有向边的图，在竞赛图上找最小支配集的答案是O(\log n)的。下面给出证明。
我们想从竞赛图上选择一个点加入最小支配集，它会带走它的出边相连的点。考虑这个点出入边各半的情况，如果在这种情况上有若干出边变为入边，那么势必会导致另外一些点的出边变多，这种情况下，选择这个点可能并不最优。也就是说，最差情况下，删除一个点会带走一半的点，每选择一个点加入最小支配集后，图的规模缩小一半。那么最小支配集的答案的规模就是是O(\log_2 n)。
既然答案不大，我们考虑迭代加深搜索，DFS来枚举看否则有合适的最小支配集。我们考虑把每个点是否被选中这个状态用一个bitset压起来，就可以搜索了。

代码

// Code by KSkun, 2018/3
#include <cstdio>

#include <bitset>

inline int read01() {
    char c = '*';
    while(c != '0' && c != '1') c = getchar();
    return c - '0';
}

const int MAXN = 105;

int kase, n, ans, ansc[MAXN];
std::bitset<MAXN> gra[MAXN], blank;

inline bool dfs(int u, int step, std::bitset<MAXN> s) {
    if(step >= ans) return s.count() == n;
    for(int v = u; v <= n; v++) {
        if(dfs((ansc[step] = v), step + 1, s | gra[v])) return true;
    }
    return false;
}

int main() {
    while(scanf("%d", &n) != EOF) {
        for(int i = 1; i <= n; i++) gra[i] = blank;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                gra[i][j] = read01();
            }
            gra[i][i] = 1;
        }
        for(ans = 1; ans <= 10; ans++) {
            if(dfs(1, 0, blank)) break;
        }
        printf("Case %d: %d ", ++kase, ans);
        for(int i = 0; i < ans; i++) printf("%d ", ansc[i]);
        printf("\n");
    }
}