匈牙利！
匈牙利算法
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
48
49
50
51
52
53
54
55
|
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=1e3+11;
const ll maxm=1e5+11;
struct Edge{
ll to,nx;
}e[maxm];
ll head[maxn],vis[maxn],match[maxn];
ll tmp=2,n1,n2,m;
void add(ll u,ll v){
e[tmp]={v};e[tmp].nx=head[u];head[u]=tmp++;
}
ll dfs(ll u){
for(ll i=head[u];i;i=e[i].nx){
ll v=e[i].to;
if(!vis[v]){
vis[v]=1;
if(!match[v] || dfs(match[v])){
cout<<v<<" "<<u<<endl;
match[v]=u;return 1;
}
}
}
return 0;
}
void solve(){
ll ans=0;
for(ll i=1;i<=n1;i++){
memset(vis,0,sizeof(vis));
if(dfs(i)) ans++;
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n1>>n2>>m;
for(ll i=1;i<=m;i++){
ll u,v;cin>>u>>v;
add(u,v+n1);add(v+n1,u);
}
solve();
return 0;
}
|
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=1e3+11;
const ll maxm=2e5+11;
struct Edge{
ll to,nx;
}e[maxm];
ll vis[maxn],match[maxn],head[maxn];
ll n,tmp;
void add(ll u,ll v){
e[tmp]={v};e[tmp].nx=head[u];head[u]=tmp++;
}
ll dfs(ll u){
for(ll i=head[u];i;i=e[i].nx){
ll v=e[i].to;
if(!vis[v]){
vis[v]=1;
if(match[v]==-1 || dfs(match[v])){
match[u]=v;match[v]=u;
return 1;
}
}
}
return 0;
}
void solve(){
for(ll i=0;i<n;i++){
memset(vis,0,sizeof(vis));
if(match[i]==-1) dfs(i);
}
ll ans=0;
for(ll i=0;i<n;i++){
if(match[i]!=-1){
ans++;
}
}
cout<<n-ans/2<<endl;
}
int main(){
while(~scanf("%lld",&n)){
memset(head,0,sizeof(head));
memset(match,-1,sizeof(match));tmp=1;
for(ll i=0;i<n;i++){
ll u,m;scanf("%lld: (%lld)",&u,&m);
for(ll j=1;j<=m;j++){
ll v;scanf("%lld",&v);
add(u,v);
}
}
solve();
}
return 0;
}
|
棋盘游戏 HDU - 1281
题意：在一个n*m（n和m < 100)的方格里，有k个方格可以放置中国象棋里的车。在尽量多放车的情况下，这k中有多少个方格删去后会导致能放的车数量减少。
思路：二分匹配模板题
因为一个方格对应了一个横坐标和一个纵坐标，所以可以将方格看成边，边的两端是其对应的横坐标与纵坐标。所以本题就转化为尽可能多的将横坐标与纵坐标匹配，为二分匹配问题。本题数据比较水，可以枚举删除的点。
Going Home HDU - 1533
题意：在一个r * c（r和c都 <100 )的地图上，有同样数量的房子和人，现要求每个人到一个房子中去，求最短路径长度。
思路：一个人一个房子，一个萝卜一个坑，又有权值，是二分最大带权匹配无疑了。但题目求的是最短路，我们只需要将其转化一下就行。此题最长路不超过200，所以我们可以将房子和人之间的路径长度l转换一下，改成200-l。这样子求最大带权匹配就ok了。