bzoj3546 [ONTAK2010]Life of the Party

题目描述

一个舞会有N个男孩(编号为1..N)和M个女孩(编号为1..M),一对男女能够组成一对跳舞当且仅当他们两个人互相认识。

我们把一种人定义成这个舞会的life:当且仅当如果他(她)不参加这个舞会,那么能够同时配对的最大舞伴对数会下降。

现在知道男生和女生之间的认识关系,需要你求出男生和女生中的是这个舞会的life的人的编号。

输入格式

第一行3个整数N,M,K,表示N个男生,M个女生,K对关系。

接下来K行,每行两个整数a_i b_i,表示第a_i个男生和第b_i个女生相互认识。

输出格式

首先输出所有男生中是这个舞会的life的男生的编号,一行一个,从小到大输出,然后输出女生的。

样例输入

4 4 4
2 1
3 2
4 3
4 4

样例输出

2
3
4
1
2

说明

N,M<=10^4,K<=10^5


分析

题目大意:求二分图的关键点,即必定在最大匹配中的点。

首先随便求一个最大匹配,那么未盖点肯定不是关键点。

判断一个匹配点是否不是关键点,只需判断是否存在以它为端点的偶交替链。如果存在,那么把交替链取反以后,这个点就变成未盖点了,那它显然不是关键点。

实现方法:偶交替链的另一个端点一定是未盖点,所以我们只需从每个未盖点开始沿交替链dfs遍历,最后没访问到的点就是关键点。

另外这题直接用匈牙利算法是$O(nm)$的,可能会超时,最好使用$O(\sqrt n m)$的dinic算法。

代码

#include <bits/stdc++.h>

const int N = 2e4+50;
const int M = 2e5+50;
const int INF = 0x3f3f3f3f;

struct Net {
    struct Graph {
        struct Edge {
            int to, nxt;
            int w;
        } e[M<<1];
        int top, head[N];

        Graph(): top(0) {
            memset(head, -1, sizeof head);
        }

        void add(int u, int v, int w) {
            e[top] = (Edge){v, head[u], w};
            head[u] = top++;
        }
    } G;

    int s, t;
    int dis[N];

    void add(int u, int v, int w) {
        G.add(u, v, w);
        G.add(v, u, 0);
    }

    bool bfs() {
        std::queue<int> q;
        memset(dis, 0, sizeof dis);
        q.push(s);
        dis[s] = 1;
        while (!q.empty() && !dis[t]) {
            int u = q.front(); q.pop();
            for (int i = G.head[u]; ~i; i = G.e[i].nxt) {
                int v = G.e[i].to, w = G.e[i].w;
                if (!w) continue;
                if (!dis[v]) {
                    dis[v] = dis[u] + 1;
                    q.push(v);
                }
            }
        }
        return dis[t];
    }

    int dfs(int u, int curFlow) {
        if (u == t) return curFlow;
        for (int i = G.head[u]; ~i; i = G.e[i].nxt) {
            int v = G.e[i].to, w = G.e[i].w, flow;
            if (w && dis[v] == dis[u] + 1 && (flow = dfs(v, std::min(curFlow, w)))) {
                G.e[i].w -= flow;
                G.e[i^1].w += flow;
                return flow;
            }
        }
        dis[u] = 0;
        return 0;
    }

    int dinic(int _s, int _t) {
        s = _s; t = _t;
        int maxFlow = 0, flow;
        while (bfs()) {
            while ((flow = dfs(s, INF)))
                maxFlow += flow;
        }
        return maxFlow;
    }
} net;

int n, m, e;
int lk[N];
bool vis[N];

void dfs(int u) {
    if (u < 1 || u > n+m || vis[u]) return;
    vis[u] = true;
    for (int i = net.G.head[u]; ~i; i = net.G.e[i].nxt) {
        int v = net.G.e[i].to;
        dfs(lk[v]);
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &e);
    for (int i = 1, u, v; i <= e; i++) {
        scanf("%d%d", &u, &v);
        net.add(u, n+v, 1);
    }
    int s = 0, t = n+m+1;
    for (int i = 1; i <= n; i++)
        net.add(s, i, 1);
    for (int i = 1; i <= m; i++)
        net.add(n+i, t, 1);
    net.dinic(s, t);

    for (int i = 0; i < 2*e; i += 2) {
        int u = net.G.e[i^1].to;
        int v = net.G.e[i].to;
        int w = net.G.e[i].w;
        if (!w) {   
            lk[u] = v;
            lk[v] = u;
        }
    }
    vis[0] = true;
    for (int i = 1; i <= n+m; i++)
        if (!lk[i]) dfs(i); 
    for (int i = 1; i <= n; i++)
        if (!vis[i]) printf("%d\n", i);
    for (int i = 1; i <= m; i++)
        if (!vis[n+i]) printf("%d\n", i);
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论