P3386 【模板】二分圖匹配

題目背景

二分圖

題目描述

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

輸入輸出格式

輸入格式：

第一行，n,m,e

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

輸出格式：

共一行，二分圖最大匹配

輸入輸出樣例

1 1 1
1 1

1

說明

n,m<=1000，1<=u<=n，1<=v<=m

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

演算法：二分圖匹配

為什麼鄰接表A不了，，，，

好奇怪，，

換上鄰接矩陣秒過，，，，

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=1001;
 7 void read(int & n)
 8 {
 9     char c='+';int x=0;bool flag=0;
10     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
11     while(c>='0'&&c<='9')x=x*10+(c-48),c=getchar();
12     flag==1?n=-x:n=x;
13 }
14 struct node
15 {
16     int u,v,nxt;
17 }edge[MAXN];
18 int head[MAXN];
19 int num=1;
20 int n,m,e;
21 void add_edge(int x,int y)
22 {
23     edge[num].u=x;
24     edge[num].v=y;
25     edge[num].nxt=head[x];
26     head[x]=num++;
27 }
28 int vis[MAXN];
29 int link[MAXN];
30 int ans=0;
31 int map[MAXN][MAXN];
32 bool dfs(int x)
33 {
34     /*for(int i=head[x];i!=-1;i=edge[i].nxt)
35     {
36         if(!vis[edge[i].v])
37         {
38             vis[edge[i].v]=1;
39             if(!link[edge[i].v]||dfs(link[edge[i].v]))
40             {
41                 link[edge[i].v]=x;
42                 return 1;
43             }
44         }
45     }
46     return 0;*/
47     for(int i=1;i<=m;i++)
48     {
49         if(map[x][i]&&!vis[i])
50         {
51             vis[i]=1;
52             if(!link[i]||dfs(link[i]))
53             {
54                 link[i]=x;
55                 return 1;
56             }
57         }
58     }
59     return 0;
60 }
61 int main()
62 {
63     memset(head,-1,sizeof(head)); 
64     read(n);read(m);read(e);
65     for(int i=1;i<=e;i++)
66     {
67         int x,y;
68         read(x);read(y);
69         if(x>n||y>m)continue;
70         //add_edge(x,y);
71         map[x][y]=1;
72     }
73     for(int i=1;i<=n;i++)
74     {
75         memset(vis,0,sizeof(vis));
76         if(dfs(i))
77             ans++;
78     }
79     printf("%d",ans);
80     return 0;
81 }