#78. 二分图最大匹配

从前一个和谐的班级，有 nlnl 个是男生，有 nrnr 个是女生。编号分别为 1,…,nl1,…,nl 和 1,…,nr1,…,nr。

有若干个这样的条件：第 vv 个男生和第 uu 个女生愿意结为配偶。

请问这个班级里最多产生多少对配偶？

输入格式

第一行三个正整数，nl,nr,mnl,nr,m。

接下来 mm 行，每行两个整数 v,uv,u 表示第 vv 个男生和第 uu 个女生愿意结为配偶。保证 1≤v≤nl1≤v≤nl，1≤u≤nr1≤u≤nr，保证同一个条件不会出现两次。

输出格式

第一行一个整数，表示最多产生多少对配偶。

接下来一行 nlnl 个整数，描述一组最优方案。第 vv 个整数表示 vv 号男生的配偶的编号。如果 vv 号男生没配偶请输出 00。

样例一

input

2 2 31 11 22 1

output

22 1

explanation

11 号男生跟 22 号女生幸福地生活在了一起～

22 号男生跟 11 号女生幸福地生活在了一起～

样例二

input

2 2 21 12 1

output

11 0

explanation

班上一个女神一个女汉子，两个男生都去追女神。一种最优方案是：

11 号男生跟 11 号女生幸福地生活在了一起～

22 号男生孤独终生。= =||

限制与约定

1≤nl,nr≤5001≤nl,nr≤500，1≤m≤2500001≤m≤250000。

时间限制：1s

空间限制：256MB

下载

分析

二分图匹配裸题

代码

 

1 #include
        
          2 #include
         
           3 #include
          
            4 #define maxn 505050 5 using namespace std; 6  7 bool vis[maxn]; 8 int matching[maxn],nl,nr,m; 9 10 struct edge{11     int from,v;12 }e[maxn];13 int tot,first[maxn];14 void insert(int u,int v){15     tot++; e[tot].from = first[u]; e[tot].v = v; first[u] = tot;16 }17 18 int dfs(int now){19     for(int i = first[now];i;i = e[i].from){20         int v = e[i].v;21         if(!vis[v]){22             vis[v] = true;23             if(!matching[v] || dfs(matching[v])){24                 matching[v] = now;25                 matching[now] = v;26                 return 1;27             }28         }29     }return 0;30 }31 32 int main(){33     scanf("%d%d%d",&nl,&nr,&m);34     35     for(int i = 1;i <= m;i++){36         int a,b;37         scanf("%d%d",&a,&b);38         b += nl;39         insert(a,b);40         insert(b,a);41     }42     43     int ans = 0;44     memset(matching,0,sizeof(matching));45     for(int i = 1;i <= nl;i++){46         if(!matching[i]){47             memset(vis,false,sizeof(vis));48             if(dfs(i))49                 ++ans;50         }51     }52     53     printf("%d\n",ans);54     for(int i = 1;i <= nl;i++){55         printf("%d ",max(matching[i]-nl,0));56     }57     58     return 0;59 }