P3386 【模板】二分图匹配

链接：P3386

这道题要用到一个名为匈牙利算法的东西

匈牙利算法就是对于每一个点，（例如A）我们先从开始找一个点（例如B），如果他们相连，并且没有被拜访过（一个点一次只能被拜访一次），就让他们配对。然而，如果B已经和C配对了，就把C赶走，看看能不能找到一个D和C配对，如果有，就让C和D配对。让A和B配对。

反之，就遍历下一个与A相连的点并重复以下步骤

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 int map[2001][2001];
 7 int n,m,e;
 8 int vis[200001];
 9 int match[2000001];
10 
11 
12 bool find (int x){
13     for(int i=1;i<=m;++i){
14         if(map[x][i]){
15             if(vis[i])
16             continue;//只能拜访一次 
17             vis[i]=1;
18             if(!match[i]||find(match[i])){//试图给他找下一个点 
19                 match[i]=x;//配对 
20                 return 1;
21             }
22             
23         }
24     }
25     return 0;
26 }
27     int cnt=0;
28 void deal(){
29 
30     memset (match,0,sizeof(match));
31     for(int i=1;i<=n;++i){
32         memset(vis,0,sizeof(vis));
33         if(find(i))
34         cnt++;//找到一个就+1 
35     }
36 }
37 
38 int main(){
39     cin>>n>>m>>e;
40     for(int i=1;i<=e;++i){
41         int x,y;
42         cin>>x>>y;
43         map[x][y]=1;
44     }
45     deal();
46     cout<<cnt;
47     return 0;
48     }

发送评论编辑评论

发送评论 编辑评论

发送评论编辑评论