P3386 【模板】二分圖最大匹配

提交71.75k

通過(guò)27.33k

時(shí)間限制1.00s

內(nèi)存限制512.00MB

提交答案加入題單

復(fù)制題目

題目提供者HOOCCOOH

難度普及+/提高

歷史分?jǐn)?shù)100

?提交記錄??查看題解

標(biāo)簽

O2優(yōu)化

?查看算法標(biāo)簽

進(jìn)入討論版

相關(guān)討論

?查看討論

推薦題目

?查看推薦

?洛谷推薦關(guān)閉

?展開(kāi)

題目描述

給定一個(gè)二分圖，其左部點(diǎn)的個(gè)數(shù)為?nn，右部點(diǎn)的個(gè)數(shù)為?mm，邊數(shù)為?ee，求其最大匹配的邊數(shù)。

左部點(diǎn)從?11?至?nn?編號(hào)，右部點(diǎn)從?11?至?mm?編號(hào)。

輸入格式

輸入的第一行是三個(gè)整數(shù)，分別代表?nn，mm?和?ee。

接下來(lái)?ee?行，每行兩個(gè)整數(shù)?u, vu,v，表示存在一條連接左部點(diǎn)?uu?和右部點(diǎn)?vv?的邊。

輸出格式

輸出一行一個(gè)整數(shù)，代表二分圖最大匹配的邊數(shù)。

輸入輸出樣例

輸入 #1復(fù)制

1 1 1 1 1

輸出 #1復(fù)制

1

輸入 #2復(fù)制

4 2 7 3 1 1 2 3 2 1 1 4 2 4 1 1 1

輸出 #2復(fù)制

2

說(shuō)明/提示

數(shù)據(jù)規(guī)模與約定

對(duì)于全部的測(cè)試點(diǎn)，保證：

• 1 \leq n, m \leq 5001≤n,m≤500。
• 1 \leq e \leq 5 \times 10^41≤e≤5×104。
• 1 \leq u \leq n1≤u≤n，1 \leq v \leq m1≤v≤m。

不保證給出的圖沒(méi)有重邊。

【AC代碼】

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; const int INF=0x3f3f3f3f; inline int read() {char ch=getchar();int n=0,m=1;while(ch<'0'||ch>'9'){if(ch=='-')m=-1;ch=getchar();}while(ch>='0'&&ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();return n*m; } void write(int n) {if(n>9)write(n/10);putchar(n%10+'0'); } int n,m,p,d[N],head[N],to[N],ne[N],id,ans; bool vis[N]; void add(int x,int y) {to[++id]=y,ne[id]=head[x],head[x]=id; } bool find(int u) {vis[u]=1;for(int i=head[u];i;i=ne[i]){int v=to[i];if(vis[d[v]])continue;if(!d[v]||find(d[v])){d[v]=u;return true;}}return false; } int main(int argc,char **argv) {n=read(),m=read(),p=read();while(p--){int x,y;x=read(),y=read();add(x,y);}for(int i=1;i<=n;i++){memset(vis,0,sizeof vis);if(find(i))ans++;}write(ans);return 0; }

總結(jié)

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

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