P14219 [ICPC 2024 Kunming I] 阻止城堡 2

· · 题解

首先删障碍不好考虑，转化为初始没有障碍，要在指定的 m - k 个位置加入障碍，要求中间有障碍的城堡对数最大。

发现加入一个障碍最多使得两对城堡产生贡献：横向的一对和纵向的一对。所以我们优先加入能使得两对城堡产生贡献的障碍，再加入能使得一对城堡产生贡献的障碍，最后若还有剩余就随便加入。

将横向相邻的一对城堡看做左部点，纵向相邻的一对城堡看做右部点，那么一个障碍如果能使两对城堡产生贡献，就可以在这两对城堡中连边，我们要求的就是二分图最大匹配。

然后加入能使得一对城堡产生贡献的障碍是简单的，直接模拟即可。

视 n, m 同阶，时间复杂度 O(n \log n + n \sqrt n)。

:::info[代码]

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 1000100;
const int inf = 0x3f3f3f3f;

int n, m, K, hd[maxn], nt, S, T, len, id1[maxn], id2[maxn], e[maxn];
bool vis[maxn], mk1[maxn], mk2[maxn];
pii c[maxn];

struct node {
    int x, y;
} a[maxn], b[maxn];

struct edge {
    int to, next, cap, flow;
} edges[maxn << 1];

inline void add_edge(int u, int v, int c, int f) {
    edges[++len].to = v;
    edges[len].next = hd[u];
    edges[len].cap = c;
    edges[len].flow = f;
    hd[u] = len;
}

struct Dinic {
    int cur[maxn], d[maxn];
    bool vis[maxn];

    inline void add(int u, int v, int c) {
        add_edge(u, v, c, 0);
        add_edge(v, u, 0, 0);
    }

    inline bool bfs() {
        for (int i = 1; i <= nt; ++i) {
            d[i] = -1;
            vis[i] = 0;
        }
        queue<int> q;
        q.push(S);
        vis[S] = 1;
        d[S] = 0;
        while (q.size()) {
            int u = q.front();
            q.pop();
            for (int i = hd[u]; i; i = edges[i].next) {
                edge &e = edges[i];
                if (!vis[e.to] && e.cap > e.flow) {
                    vis[e.to] = 1;
                    d[e.to] = d[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return vis[T];
    }

    int dfs(int u, int a) {
        if (u == T || !a) {
            return a;
        }
        int flow = 0, f;
        for (int &i = cur[u]; i; i = edges[i].next) {
            edge &e = edges[i];
            if (d[e.to] == d[u] + 1 && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
                e.flow += f;
                edges[i ^ 1].flow -= f;
                flow += f;
                a -= f;
                if (!a) {
                    break;
                }
            }
        }
        return flow;
    }

    inline int solve() {
        int flow = 0;
        while (bfs()) {
            for (int i = 1; i <= nt; ++i) {
                cur[i] = hd[i];
            }
            flow += dfs(S, inf);
        }
        return flow;
    }
} solver;

void solve() {
    len = 1;
    for (int i = 0; i <= nt; ++i) {
        hd[i] = 0;
    }
    nt = 0;
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &a[i].x, &a[i].y);
        id1[i] = id2[i] = 0;
        mk1[i] = mk2[i] = 0;
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &b[i].x, &b[i].y);
        vis[i] = 0;
    }
    K = m - K;
    map< int, set<pii> > mp1, mp2;
    for (int i = 1; i <= n; ++i) {
        mp1[a[i].x].emplace(a[i].y, i);
        mp2[a[i].y].emplace(a[i].x, i);
    }
    S = ++nt;
    T = ++nt;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        auto it = mp1[a[i].x].find(pii(a[i].y, i));
        if (next(it) != mp1[a[i].x].end()) {
            id1[i] = ++nt;
            ++ans;
            solver.add(S, id1[i], 1);
        }
        it = mp2[a[i].y].find(pii(a[i].x, i));
        if (next(it) != mp2[a[i].y].end()) {
            id2[i] = ++nt;
            ++ans;
            solver.add(id2[i], T, 1);
        }
    }
    for (int i = 1; i <= m; ++i) {
        e[i] = 0;
        c[i] = pii(0, 0);
        if (mp1.find(b[i].x) != mp1.end()) {
            auto it = mp1[b[i].x].lower_bound(pii(b[i].y, 0));
            if (it != mp1[b[i].x].end() && it != mp1[b[i].x].begin()) {
                c[i].fst = prev(it)->scd;
            }
        }
        if (mp2.find(b[i].y) != mp2.end()) {
            auto it = mp2[b[i].y].lower_bound(pii(b[i].x, 0));
            if (it != mp2[b[i].y].end() && it != mp2[b[i].y].begin()) {
                c[i].scd = prev(it)->scd;
            }
        }
        int x = c[i].fst, y = c[i].scd;
        if (x && y) {
            solver.add(id1[x], id2[y], 1);
            e[i] = len - 1;
        }
    }
    solver.solve();
    int cnt = K;
    for (int i = 1; i <= m; ++i) {
        if (!e[i]) {
            continue;
        }
        int j = e[i];
        if (edges[j].flow) {
            if (cnt) {
                --cnt;
                ans -= 2;
                vis[i] = 1;
                mk1[c[i].fst] = mk2[c[i].scd] = 1;
            }
        }
    }
    for (int i = 1; i <= m; ++i) {
        if (vis[i]) {
            continue;
        }
        if (cnt && ((c[i].fst && !mk1[c[i].fst]) || (c[i].scd && !mk2[c[i].scd]))) {
            --cnt;
            --ans;
            vis[i] = 1;
            if (c[i].fst) {
                mk1[c[i].fst] = 1;
            }
            if (c[i].scd) {
                mk2[c[i].scd] = 1;
            }
        }
    }
    for (int i = 1; i <= m; ++i) {
        if (!vis[i] && cnt) {
            --cnt;
            vis[i] = 1;
        }
    }
    printf("%d\n", ans);
    for (int i = 1; i <= m; ++i) {
        if (vis[i]) {
            continue;
        }
        printf("%d ", i);
    }
    putchar('\n');
}

int main() {
    int T = 1;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}

:::