题目链接

https://www.luogu.com.cn/problem/P6113

题目大意

给定一个 \(n\) 个点 \(m\) 条边的无向图，求该图的最大匹配。

题目解析

二分图最大匹配，一般用匈牙利算法完成，图中只存在偶环。

而一般图不能分为左右两部，存在奇环，如何处理奇环，是带花树算法的关键。

若将偶环缩为一点，则该图可以简化为只有奇环的无向图。

对于奇环内部，两两匹配后必定多出一个点不能匹配，则将该点与环外部的点相匹配即可。

通过类似匈牙利算法的多次增广，可以找到最大匹配。

点数为 \(n\)，边数为 \(m\) 。

时间复杂度： \(O(n^2 m)\)

参考代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int  n, m, cnt;

int fa[N], vis[N], tag[N], pre[N], match[N];

queue <int> q;

vector <int> e;

vector <int> G[N];

void addEdge(int a, int b, int i)

{

    e.push_back(b);

    e.push_back(a);

    G[a].push_back(i);

    G[b].push_back(i ^ 1);

}

inline int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}

inline int lca(int x, int y)

{

    ++cnt;

    while (true)

    {

        if (x)

        {

            x = find(x);

            if (tag[x] == cnt) return x;

            tag[x] = cnt;

            x = pre[match[x]];

        }

        swap(x, y);

    }

}

inline void blossom(int x, int y, int p)

{

    while (find(x) != p)

    {

        pre[x] = y; y = match[x];

        vis[y] = 1; q.push(y);

        if (find(x) == x) fa[x] = p;

        if (find(y) == y) fa[y] = p;

        x = pre[y];

    }

}

bool bfs(int s)

{

    for (int i = 1; i <= n; ++i) vis[i] = pre[i] = 0, fa[i] = i;

    while (!q.empty()) q.pop();

    q.push(s);

    vis[s] = 1;

    while (!q.empty())

    {

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

        for (int i = 0; i < G[u].size(); ++i)

        {

            int v = e[G[u][i]];

            if (vis[v] == 2 || find(u) == find(v)) continue;

            if (!vis[v])

            {

                vis[v] = 2, pre[v] = u;

                if (!match[v])

                {

                    int x = v;

                    while (x)

                    {

                        int y = pre[x], z = match[y];

                        match[x] = y, match[y] = x;

                        x = z;

                    }

                    return 1;

                }

                vis[match[v]] = 1;

                q.push(match[v]);

            }

            else

            {

                int p = lca(u, v);

                blossom(u, v, p);

                blossom(v, u, p);

            }

        }

    }

    return 0;

}

int main()

{

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

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

        int a, b;

        scanf("%d%d", &a, &b);

        addEdge(a, b, i << 1);

    }

    int ans = 0;

    for (int i = 1; i <= n; ++i) if (!match[i] && bfs(i)) ans++;

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

    for (int i = 1; i <= n; i++) printf("%d%c", match[i], i == n ? '\n' : ' ');

    return 0;

}

感谢支持！

巴特西

【模板】一般图最大匹配（带花树算法）/洛谷P6113

题目链接

题目大意

题目解析

参考代码

最新文章

热门文章