题解 CF1721F 【Matching Reduction】

· · 题解

前置芝士：二分图、最大流

注意到题目中讨论的是删点而非删边，考虑将最大匹配转化为点数减去最大独立集。

为了将最大匹配减少 1，我们显然可以只删除一个不在最大独立集中的点。

我们已知最大独立集的补集为最小点覆盖，于是我们可以通过求最大匹配间接求出最大独立集。具体地，我们在本题中使用最大流求最大匹配，在残量网络上从 S 开始 dfs 并标记访问过的点，最终左部点中未被访问的点和右部点中被访问的点在最大独立集中。

对于操作 1，随意选择最大独立集中的一个点删除并删除与之相连的匹配边。

对于操作 2，数一下还有多少条匹配边并直接输出匹配边即可。

时间复杂度为 O(n1 + n2 + m \sqrt{n1 + n2} + q)。

代码：

#include <queue>
#include <cstdio>

using namespace std;

typedef long long ll;

typedef struct {
    int nxt;
    int start;
    int end;
    int dis;
} Edge;

int cnt = 1;
int head[400007], id[200007], dis[400007], cur_edge[400007], dis_cnt[400007], candiate[400007], link[400007];
bool vis[400007], mark[200007];
Edge edge[1200007];
queue<int> q;

inline void init(int n){
    for (register int i = 0; i <= n; i++){
        dis[i] = 0x7fffffff;
        cur_edge[i] = head[i];
    }
}

inline void add_edge(int start, int end, int dis){
    cnt++;
    edge[cnt].nxt = head[start];
    head[start] = cnt;
    edge[cnt].start = start;
    edge[cnt].end = end;
    edge[cnt].dis = dis;
}

inline void bfs(int start){
    dis[start] = 0;
    q.push(start);
    while (!q.empty()){
        int cur = q.front(), dis_i = dis[cur] + 1;
        q.pop();
        dis_cnt[dis[cur]]++;
        for (register int i = head[cur]; i != 0; i = edge[i].nxt){
            int x = edge[i].end;
            if (dis[x] == 0x7fffffff){
                dis[x] = dis_i;
                q.push(x);
            }
        }
    }
}

int dfs1(int u, int flow, int start, int end, int n){
    if (u == end) return flow;
    int ans = 0;
    for (register int i = cur_edge[u]; i != 0; i = edge[i].nxt){
        cur_edge[u] = i;
        if (edge[i].dis != 0){
            int x = edge[i].end;
            if (dis[u] == dis[x] + 1){
                int t = dfs1(x, min(flow - ans, edge[i].dis), start, end, n);
                edge[i].dis -= t;
                edge[i ^ 1].dis += t;
                ans += t;
                if (ans == flow) return ans;
            }
        }
    }
    cur_edge[u] = head[u];
    if (--dis_cnt[dis[u]] == 0) dis[start] = n;
    dis_cnt[++dis[u]]++;
    return ans;
}

inline int isap(int start, int end, int n){
    int ans = 0;
    bfs(end);
    while (dis[start] < n) ans += dfs1(start, 0x7fffffff, start, end, n);
    return ans;
}

void dfs2(int u){
    vis[u] = true;
    for (register int i = head[u]; i != 0; i = edge[i].nxt){
        if (edge[i].dis != 0){
            int x = edge[i].end;
            if (!vis[x]) dfs2(x);
        }
    }
}

int main(){
    int n1, n2, m, q, end, candiate_cnt = 0;
    ll sum = 0;
    scanf("%d %d %d %d", &n1, &n2, &m, &q);
    end = n1 + n2 + 1;
    for (register int i = 1; i <= m; i++){
        int x, y, y_;
        scanf("%d %d", &x, &y);
        y_ = y + n1;
        add_edge(x, y_, 1);
        id[i] = cnt;
        add_edge(y_, x, 0);
    }
    for (register int i = 1; i <= n1; i++){
        add_edge(0, i, 1);
        add_edge(i, 0, 0);
    }
    for (register int i = 1; i <= n2; i++){
        int i_ = i + n1;
        add_edge(i_, end, 1);
        add_edge(end, i_, 0);
    }
    init(end);
    isap(0, end, end + 1);
    dfs2(0);
    for (register int i = 1; i <= n1; i++){
        if (!vis[i]) candiate[++candiate_cnt] = i;
    }
    for (register int i = 1; i <= n2; i++){
        int i_ = i + n1;
        if (vis[i_]) candiate[++candiate_cnt] = i_;
    }
    for (register int i = 1; i <= m; i++){
        if (edge[id[i]].dis == 0){
            sum += i;
            link[edge[id[i]].start] = link[edge[id[i]].end] = i;
            mark[i] = true;
        }
    }
    for (register int i = 1, j = 0; i <= q; i++){
        int op;
        scanf("%d", &op);
        if (op == 1){
            int u = candiate[++j];
            printf("1\n");
            if (u <= n1){
                printf("%d\n", u);
            } else {
                printf("%d\n", -(u - n1));
            }
            if (mark[link[u]]){
                mark[link[u]] = false;
                sum -= link[u];
            }
            printf("%lld\n", sum);
        } else {
            int size = 0;
            for (register int k = 1; k <= m; k++){
                if (mark[k]) size++;
            }
            printf("%d\n", size);
            for (register int k = 1; k <= m; k++){
                if (mark[k]) printf("%d ", k);
            }
            printf("\n");
        }
        fflush(stdout);
    }
    return 0;
}