UOJ 78: 二分图最大匹配

2018-03-27Chentiancai_nn?

从前一个和谐的班级,有 $n_l$ 个是男生,有 $n_r$ 个是女生。编号分别为 $1,…,nl$ 和 $1,…,nr$。

有若干个这样的条件:第 $v$ 个男生和第 $u$ 个女生愿意结为配偶。

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

输入格式

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

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

输出格式

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

接下来一行 $nl$ 个整数,描述一组最优方案。第 $v$ 个整数表示 $v$ 号男生的配偶的编号。如果 $v$ 号男生没配偶请输出 $0$。

样例一

input

2 2 3
1 1
1 2
2 1

output

2
2 1

explanation

$1$ 号男生跟 $2$ 号女生幸福地生活在了一起~

$2$ 号男生跟 $1$ 号女生幸福地生活在了一起~

样例二

input

2 2 2
1 1
2 1

output

1
1 0

explanation

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

$1$ 号男生跟 $1$ 号女生幸福地生活在了一起~

$2$ 号男生孤独终生。= =||

限制与约定

$1≤nl,nr≤500$,$1≤m≤250000$。

时间限制:$1s$

空间限制:$256MB$

题解

只是用来存板子的,可以使用匈牙利和dinic

代码

这是匈牙利算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
int x = 0,f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();}
return x*f;
}

const int N = 505,M = 250005;
int n1,n2,m,link[N*2],Ans[N*2];
bool vis[N*2];
bool mp[N][N];

inline bool dfs(int x){
for(int i = 1;i <= n2;++i)
if((!vis[i]) && mp[x][i]){
vis[i] = true;
if(link[i] == 0 || dfs(link[i])){
link[i] = x;
return true;
}
}
return false;
}

int main(){
n1 = read();n2 = read(); m = read();
// memset(head,-1,sizeof head);
for(int i = 1;i <= m;++i){
int x = read(),y = read();
mp[x][y] = true;
}
int ans = 0;
for(int i = 1;i <= n1;++i){
memset(vis,false,sizeof(bool)*(n1+n2+1));
if(dfs(i)) ++ans;
}
printf("%d\n", ans);
for(int i = 1;i <= n2;++i)
Ans[link[i]] = i;
for(int i = 1;i <= n1;++i)
printf("%d ", Ans[i]);
puts("");
return 0;
}

检测到你还在使用百度这个搜索引擎,
做为一个程序员,这是一种自暴自弃!

作环保的程序员,从不用百度开始!

Close