Codeforces 1525F 二分图最小点覆盖 + DP

传送门 Codeforces 1525F Goblins And Gnomes

若 DAG 的最小路径覆盖数小于等于哥布林数，则必败。DAG 的最小路径覆盖是一个经典问题，可以转换为求解拆点二分图的最大匹配。只删除图中某个节点的出边或入边等价于删除二分图上的某个节点，最大化收益则需要删除的点数尽可能小，那删除二分图最大匹配的必经点可以满足要求。若必经点存在，需要 O ( n ) O(n) O(n) 依次删除节点， O ( n 3 ) O(n^3) O(n3) 枚举节点判断是否将其删除后最大匹配数减少一。这样处理 O ( n 4 ) O(n^4) O(n4)，实际上求解删除节点序列可以做到 O ( n 3 ) O(n^3) O(n3)。

二分图的最小点覆盖等于最大匹配。以任意次序删除二分图的最小点覆盖可以发现，最大匹配数依次减少一。那么问题中删除的点集就是最小点覆盖的某个子集。

二分图最小点覆盖可以 O ( n m ) O(nm) O(nm) 求解。最后 D P DP DP 依次枚举一波攻击删除的点数即可。总时间复杂度 O ( n 3 ) O(n^3) O(n3)。

#include 
using namespace std;
using ll = long long;
constexpr int MAXN = 105;
int N, M, K;
vector G[MAXN];
int X[MAXN], Y[MAXN];
bool used[MAXN];
int match[MAXN], pre[MAXN][MAXN];
ll dp[MAXN][MAXN];

bool dfs(int v)
{
    used[v] = 1;
    for (int u : G[v])
    {
        int w = match[u];
        if (w == -1 || (!used[w] && dfs(w)))
        {
            match[u] = v, match[v] = u;
            return 1;
        }
    }
    return 0;
}

void find(int v)
{
    used[v] = 1;
    for (int u : G[v])
    {
        used[u] = 1;
        int w = match[u];
        if (!used[w])
            find(w);
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N >> M >> K;
    for (int i = 0; i < M; ++i)
    {
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[u].push_back(N + v);
    }
    for (int i = 0; i < K; ++i)
        cin >> X[i] >> Y[i];
    memset(match, -1, sizeof(match));
    int s = 0;
    for (int i = 0; i < N; ++i)
        memset(used, 0, sizeof(used)), s += dfs(i);
    memset(used, 0, sizeof(used));
    for (int i = 0; i < N; ++i)
        if (match[i] == -1)
            find(i);
    vector vs;
    for (int i = 0; i < N; ++i)
        if (!used[i])
            vs.push_back(i + 1);
    for (int i = 0; i < N; ++i)
        if (used[N + i])
            vs.push_back(-(i + 1));
    assert(vs.size() == s);
    memset(dp, 0xc0, sizeof(dp));
    memset(pre, -1, sizeof(pre));
    dp[0][s] = 0;
    for (int i = 0; i < K; ++i)
        for (int j = 0; j <= s; ++j)
            for (int k = min(j, N - (i + 2)); k >= 0; --k)
            {
                ll t = max(0ll, X[i] - (ll)(j - k) * Y[i]);
                if (dp[i + 1][k] < dp[i][j] + t)
                    dp[i + 1][k] = dp[i][j] + t, pre[i + 1][k] = j;
            }
    int num = -1;
    for (int i = N - (K + 1); i >= 0; --i)
        if (num == -1 || dp[K][i] > dp[K][num])
            num = i;
    vector> act(K);
    for (int i = K, j = num; i; --i)
    {
        for (int k = j; k < pre[i][j]; ++k)
            act[i - 1].push_back(vs[k]);
        j = pre[i][j];
    }
    int sum = 0;
    for (int i = 0; i < K; ++i)
        sum += act[i].size() + 1;
    cout << sum << 'n';
    for (int i = 0; i < K; ++i)
    {
        for (int a : act[i])
            cout << a << ' ';
        cout << "0 ";
    }
    return 0;
}