1143, 3997: Dilworth定理的简单应用

偏序集上的最小链覆盖等价于求最长反链

最小不交链覆盖等于传递闭包后最小链覆盖

最小链覆盖大小等于点数减去二分图最大匹配大小

二分图最小点覆盖大小等于二分图匹配大小

二分图最小点覆盖与二分图最大独立集对偶

建图完后，这个二分图最大独立集等价于最长反链。

于是两道题

1143: [CTSC2008]祭祀river

求偏序集上的最长反链

转换成偏序集上的最小链覆盖

求个闭包，转换成最小路径覆盖，二分图匹配一发

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

const int MAXN = 210;

const int MAXM = MAXN * MAXN * 2;

const int INF = 0x3f3f3f3f;

int head[MAXN], nxt[MAXM], to[MAXM], val[MAXM], tot = 1;

inline void addedge(int b, int e, int v) {

    nxt[++tot] = head[b]; to[head[b] = tot] = e; val[tot] = v;

    nxt[++tot] = head[e]; to[head[e] = tot] = b; val[tot] = 0;

}

std::queue<int> q;

int S, T, dis[MAXN];

bool bfs() {

    for (int i = S; i <= T; ++i) dis[i] = 0;

    dis[S] = 1; q.push(S);

    while (!q.empty()) {

        int t = q.front(); q.pop();

        for (int i = head[t]; i; i = nxt[i])

            if (val[i] && !dis[to[i]]) {

                dis[to[i]] = dis[t] + 1;

                q.push(to[i]);

            }

    }

    return dis[T] > 0;

}

int dinic(int u, int minv) {

    if (u == T || !minv) return minv;

    int t, res = 0;

    for (int i = head[u]; i; i = nxt[i])

        if (val[i] && dis[to[i]] == dis[u] + 1 && (t = dinic(to[i], std::min(minv, val[i])))) {

            val[i] -= t;

            val[i ^ 1] += t;

            res += t;

            minv -= t;

            if (!minv) break;

        }

    if (!res) dis[u] = -1;

    return res;

}

int n, m, t1, t2, f[MAXN][MAXN];

int main() {

    scanf("%d%d", &n, &m);

    S = 0, T = n << 1 | 1;

    for (int i = 1; i <= m; ++i) {

        scanf("%d%d", &t1, &t2);

        f[t1][t2] = true;

    }

    for (int k = 1; k <= n; ++k)

        for (int i = 1; i <= n; ++i)

            for (int j = 1; j <= n; ++j)

                f[i][j] |= f[i][k] & f[k][j];

    for (int i = 1; i <= n; ++i)

        for (int j = 1; j <= n; ++j)

            if (f[i][j])

                addedge(i, j + n, 1);

    for (int i = 1; i <= n; ++i) {

        addedge(S, i, 1);

        addedge(i + n, T, 1);

    }

    int ans = n;

    while (bfs()) ans -= dinic(S, INF);

    printf("%d\n", ans);

    return 0;

}

3997: [TJOI2015]组合数学

 给出一个网格图，其中某些格子有财宝，每次从左上角出发，只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形，假设每个格子中有好多财宝，而每一次经过一个格子至多只能捡走一块财宝，至少走多少次才能把财宝全部捡完。

求偏序集上的最小链覆盖，转换为最长反链覆盖

于是只要DP出反链就好了，前(其实是后)缀和优化一下

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

const int MAXN = 1010;

int f[MAXN][MAXN], suc[MAXN][MAXN], map[MAXN][MAXN], n, m;

inline void getmax(int & x, const int y) { if (x < y) x = y; }

int main() {

    int T; scanf("%d", &T);

    while (T --> 0) {

        scanf("%d%d", &n, &m);

        for (int i = 0; i <= n + 1; ++i)

            for (int j = 0; j <= m + 1; ++j)

                f[i][j] = suc[i][j] = 0;

        for (int i = 1; i <= n; ++i) {

            for (int j = 1; j <= m; ++j) scanf("%d", map[i] + j);

            for (int j = m; j; --j) {

                getmax(f[i][j], suc[i - 1][j + 1] + map[i][j]);

                suc[i][j] = std::max(suc[i][j + 1], suc[i - 1][j]);

                getmax(suc[i][j], f[i][j]);

            }

        }

        printf("%d\n", suc[n][1]);

    }

    return 0;

}

巴特西

1143, 3997: Dilworth定理的简单应用

1143: [CTSC2008]祭祀river

3997: [TJOI2015]组合数学

最新文章

热门文章