?展開

題目背景

二分圖

感謝@一扶蘇一 提供的hack數據

題目描述

給定一個二分圖，結點個數分別為n,m，邊數為e，求二分圖最大匹配數

輸入格式

第一行，n,m,e

第二至e+1行，每行兩個正整數u,v，表示u,v有一條連邊

輸出格式

共一行，二分圖最大匹配

輸入輸出樣例

輸入 #1復制

1 1 1 1 1

輸出 #1復制

1

因為數據有坑，可能會遇到?v>m?或者?u>n?的情況。請把?v>m?或者?u>n的數據自覺過濾掉。

算法：二分圖匹配

AC Code:

#include<iostream> #include<cstring> #include<queue> #include<map> #include<set> #include<stack> #include<cstdio> #include<sstream> #include<vector> #include<bitset> #include<algorithm>using namespace std; #define read(x) scanf("%d",&x) #define Read(x,y) scanf("%d%d",&x,&y) #define gc(x) scanf(" %c",&x); #define mmt(x,y) memset(x,y,sizeof x) #define write(x) printf("%d\n",x) #define pii pair<int,int> #define INF 0x3f3f3f3f #define ll long long const ll mod = 998244353; const int N = 1e6 + 1000; const int M = 2e6 + 1005; struct Edge {int next;int to; }edge[N]; int head[N],tot; inline void add(int from,int to){edge[++tot].next = head[from];edge[tot].to = to;head[from] = tot; } bool vis[N];int match[N]; bool dfs(int x){for(int i = head[x],y;~i;i = edge[i].next){if(!vis[y = edge[i].to]){vis[y] = 1;if(!match[y]||dfs(match[y])){match[y] = x;return true;}}}return false; } inline void init(){mmt(head,-1);tot = 0; } int main() {int n,m,k;Read(n,m);read(k);int u,v;init();for(int i =1 ;i <= k;++i){Read(u,v);if(u > n||v > m) continue;add(u,v + n);add(v + n,u);}int ans = 0;for(int i = 1;i <= n + m ;++i){mmt(vis,0);if(dfs(i)) ans ++;}cout<<ans<<endl; }

?

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。