首页 > > 程序设计 > C/C++ >

P3386 【模板】二分图匹配

2018-06-17 22:10:56来源：未知阅读 ()

题目背景

二分图

题目描述

给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数

输入输出格式

输入格式：

第一行，n,m,e

第二至e+1行，每行两个正整数u,v，表示u,v有一条连边

输出格式：

共一行，二分图最大匹配

输入输出样例

输入样例#1：

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 }