題目鏈接：點(diǎn)擊這里

題目大意：
給定一個(gè)二分圖，其左部點(diǎn)的個(gè)數(shù)為 $n$ ，右部點(diǎn)的個(gè)數(shù)為 $m$ ，邊數(shù)為 $e$ ，求其最大匹配的邊數(shù)。

題目分析：
本題使用的匈牙利算法完成的二分圖最大匹配

具體細(xì)節(jié)見代碼：

// Problem: P3386 【模板】二分圖最大匹配 // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P3386 // Memory Limit: 512 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<set> #include<map> #include<stack> #include<queue> #include<unordered_map> #define ll long long #define inf 0x3f3f3f3f #define Inf 0x3f3f3f3f3f3f3f3f //#define int ll #define endl '\n' #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) using namespace std; int read() {int res = 0,flag = 1;char ch = getchar();while(ch<'0' || ch>'9'){if(ch == '-') flag = -1;ch = getchar();}while(ch>='0' && ch<='9'){res = (res<<3)+(res<<1)+(ch^48);//res*10+ch-'0';ch = getchar();}return res*flag; } const int maxn = 1e3+5; const int mod = 1e9+7; const double pi = acos(-1); const double eps = 1e-8; int n,m,e,mp[maxn][maxn],p[maxn]; bool vis[maxn]; bool match(int id) {for(int i = 1;i <= m;i++){if(mp[id][i] && !vis[i]){vis[i] = true;if(!p[i] || match(p[i])) {p[i] = id;return true;}}}return false; } int main() {n = read(),m = read(),e = read();for(int i = 1;i <= e;i++){int u = read(),v = read();mp[u][v] = 1;}int res = 0;for(int i = 1;i <= n;i++) {for(int j = 1;j <= m;j++) vis[j] = 0;if(match(i)) res++;}cout<<res<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的P3386 【模板】二分图最大匹配（匈牙利算法模板）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。