「Bzoj 1143」「CTSC2008」祭祀 (Dilworth定理 + 二分图匹配(最小链覆盖))

发表于 | 分类于 | | + s

Bzoj 1143
题意：见上。

补充两个问题 (Luogu题面)

接下来一行输出一种可行的选取方案。对于每个岔口依次输出一个整数，如果在该岔口设置了祭祀点，那么输出一个$1$，否则输出一个$0$。应确保你输出的$1$的个数最多，且中间没有空格。 接下来一行输出，在选择最多祭祀点的前提下，每个岔口是否能够设置祭祀点。对于每个岔口依次输出一个整数，如果在该岔口能够设置祭祀点，那么输出一个$1$，否则输出一个$0$。

本题就是求一个最长反链。Dilworth定理转化为最小链覆盖。
然后二分图匹配求最小链覆盖(最大独立集)即可。
对于输出方案，可以取反最小点覆盖的方案，具体看算法竞赛进阶指南相关内容。
对于第三问，我们考虑枚举点，然后删掉这个点所有可以到达的点和删掉所有可以到达这个点的点，求一次最大独立集，如果少了1，则这个点是可以的。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 100 + 5;

    int n, m, f[MAXN][MAXN], g[MAXN][MAXN], cnt, vis[MAXN], lk[MAXN];

    bool hungary(int u) {
        for (int v = 1; v <= n; ++v) {
            if (g[u][v]) {
                if (vis[v] != cnt) {
                    vis[v] = cnt;
                    if (!lk[v] || hungary(lk[v])) {
                        lk[v] = u;
                        return true;
                    }
                }
            }
        }
        return false;
    }

    void clean() {
        ms(f, 0), ms(vis, 0), ms(lk, 0);
    }
    int solve() {

        clean();
        cin >> n >> m;
        for (int x, y, i = 1; i <= m; ++i) {
            scanf("%d%d", &x, &y);
            f[x][y] = 1;
        }

        //Floyd
        for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) if (i != j && i != k && j != k)
            f[i][j] |= (f[i][k] & f[k][j]);

        memcpy(g, f, sizeof f);
        int ans = 0;
        for (int i = 1; i <= n; ++i) ans += hungary(cnt = i);
        printf("%d\n", n - ans);


        return 0;
    }
}
int main() { 
    flyinthesky::solve();
    return 0;
}
/*
*/
------ 本文结束 ------