定义从未匹配点出发,依次经过匹配边、非匹配边、匹配边......所形成的路径叫交替路,从一个未匹配点出发,走交替路,如果途径另一个未匹配点(起始点不包括),则这条交替路称为增广路

通过不停地找增广路来增加匹配中的匹配边和匹配点,当找不到增广路时,可以获得二分图的最大匹配。

算法时间复杂度$O(|V|*|E|)$。

//luogu P3386
#include <bits/stdc++.h>
using namespace std;

const int N = 1001;

int n, m, e;
bool G[N][N];
bool vis[N];
int match_y[N];
int ans;

bool match(int x) {
    for ( int y = 1; y <= m; ++y ) {
        if ( !vis[y] && G[x][y] ) {
            vis[y] = true;
            if ( match_y[y] == -1 || match(match_y[y]) ) {
                match_y[y] = x;

                return true;
            }
        }
    }

    return false;
}

int main() {
    ios::sync_with_stdio(false);

    cin >> n >> m >> e;

    int u, v;
    for ( int i = 1; i <= e; ++i ) {
        cin >> u >> v;

        if ( u <= n && v <= m )
            G[u][v] = true;
    }

    memset(match_y, -1, sizeof match_y);
    for ( int i = 1; i <= n; ++i ) {
        ans += match(i);
        memset(vis, 0, sizeof vis);
    }

    cout << ans << endl;

    return 0;
}

拓展资料:

Last modification:November 28th, 2019 at 06:52 pm
博客维护不易,如果你觉得我的文章有用,请随意赞赏