二分图专题补

自用笔记算法

二分图专题补

la4043

题目要求

白书P351
平面内有n个白点和n个黑点 点和点的边权为欧几里德距离
问能否有一种匹配方案 使得一个白点恰好连接另一个黑点 并且所有的线段不相交

参考AC代码

1
2
3
权值取负带入km模版
注意km模版改成double
最后输出i和linker[i]即可

思路

证明见白书P351

uva 11383

题目要求

白书P351
给出一个N×N的矩阵 每个格子里都有一个正整数w(i,j) 现在要给每一行确定一个整数row(i) 每列也确定一个整数col(i)
使得对于任意一个格子(i,j) w(i,j)<=row(i)+col(j) 所有的row(i)+col(i)应当尽可能小

参考AC代码

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
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
#define maxn 505
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int nx,ny;
int g[maxn][maxn];
int linker[maxn],lx[maxn],ly[maxn];
int slack[maxn];
bool visx[maxn],visy[maxn];
bool dfs(int x){
	visx[x]=true;
	for(int y=0;y<ny;y++){
		if(visy[y]) continue;
		int tmp=lx[x]+ly[y]-g[x][y];
		if(tmp==0){
			visy[y]=true;
			if(linker[y]==-1 || dfs(linker[y])){
				linker[y]=x;
				return true;
			}
		}
		else slack[y]=min(slack[y],tmp);
	}
	return false;
}
int km(){
	mm(linker,-1),mm(ly,0);
	for(int i=0;i<nx;i++){
		lx[i]=g[i][0];
		for(int j=1;j<ny;j++) lx[i]=max(lx[i],g[i][j]);
	}
	for(int i=0;i<nx;i++){
		fill(slack,slack+ny,inf);
		while(1){
			mm(visx,false),mm(visy,false);
			if(dfs(i)) break;
			int d=inf;
			for(int j=0;j<ny;j++){
				if(!visy[j]) d=min(d,slack[j]);
			}
			for(int j=0;j<nx;j++){
				if(visx[j]) lx[j]-=d;
			}
			for(int j=0;j<ny;j++){
				if(visy[j]) ly[j]+=d;
				else slack[j]-=d;
			}
		}
	}
	int ans=0;
	for(int i=0;i<ny;i++){
		if(linker[i]!=-1) ans+=g[linker[i]][i];
	}
	return ans;
}
int main(){
//	freopen("input.txt","r",stdin);
	int n;
	while(scanf("%d",&n)!=EOF){
		nx=ny=n;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++) scanf("%d",&g[i][j]);
		}
		int ans=km();
		for(int i=0;i<nx;i++){
			if(i==nx-1) printf("%d\n",lx[i]);
			else printf("%d ",lx[i]);
		}
		for(int i=0;i<ny;i++){
			if(i==ny-1) printf("%d\n",ly[i]);
			else printf("%d ",ly[i]);
		}
		printf("%d\n",ans);
	}
	return 0;
}

思路

km算法原理
km算法里有一个重要的不等式lx(x)+ly(y)>=w(x,y) 正好是这题所需要的条件
所以对原数组g带入km模版后 实际的效果就是
所有的lx和ly数组和最小 并且每一个位置(x,y) 满足w(x,y)<=lx[x]+ly[y]

la3989(稳定婚姻问题)

题目要求

白书P352

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 1050
using namespace std;
int pref[maxn][maxn],order[maxn][maxn],nxt[maxn];
int future_husband[maxn],future_wife[maxn];
queue<int>q;
void engage(int man,int woman){
	int m=future_husband[woman];
	if(m){
		future_wife[m]=0;
		q.push(m);
	}
	future_wife[man]=woman;
	future_husband[woman]=man;
}
int main(){
//	freopen("input.txt","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		while(!q.empty()) q.pop();
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++) scanf("%d",&pref[i][j]);
			nxt[i]=1;
			future_wife[i]=0;
			q.push(i);
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				int x;
				scanf("%d",&x);
				order[i][x]=j;
			}
			future_husband[i]=0;
		}
		while(!q.empty()){
			int man=q.front();
			q.pop();
			int woman=pref[man][nxt[man]++];
			if(!future_husband[woman]) engage(man,woman);
			else if(order[woman][man]<order[woman][future_husband[woman]]) engage(man,woman);
			else q.push(man);
		}
		for(int i=1;i<=n;i++) printf("%d\n",future_wife[i]);
		if(t) puts("");
	}	
	return 0;
}

思路

白书P352

uva 11419

题目要求

白书P355
本题与如下题目相似
转跳链接

参考AC代码

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
65
66
#include<bits/stdc++.h>
#define maxn 1050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,m,k;
int g[maxn][maxn];
bool used_l[maxn],used_r[maxn];
int le[maxn],ri[maxn];
vector<int>x,y;
bool dfs(int u){
	used_r[u]=true;
	for(int i=1;i<=m;i++){
		if(g[u][i] && !used_l[i]){
			used_l[i]=true;
			if(le[i]==-1 || dfs(le[i])){
				le[i]=u;
				ri[u]=i;
				return true;
			}
		}
	}
	return false;
}
int hungary(){
	int ans=0;
	mm(le,-1);
	mm(ri,-1);
	for(int i=1;i<=n;i++){
		mm(used_l,0);
		mm(used_r,0);
		if(dfs(i)) ans++;
	}
	return ans;
}
void get_way(){
	mm(used_l,0),mm(used_r,0);
	for(int i=1;i<=n;i++){
		if(ri[i]==-1) dfs(i);
	}
	for(int i=1;i<=n;i++){
		if(!used_r[i]) x.push_back(i);
	}
	for(int i=1;i<=m;i++){
		if(used_l[i]) y.push_back(i);
	}
}
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d%d",&n,&m,&k)!=EOF){
		if(n==0 && m==0 && k==0) break;
		mm(g,0);
		x.clear(),y.clear();
		for(int i=1;i<=k;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			g[x][y]=1;
		}
		int ans=hungary();
		get_way();
		printf("%d",ans);
		for(int i=0;i<x.size();i++) printf(" r%d",x[i]);
		for(int i=0;i<y.size();i++) printf(" c%d",y[i]);
		puts("");
	}
	return 0;
}

思路

与转跳链接里题目的区别在于：本题没有障碍物 一次可以直接覆盖一行或者一列 所以不需要build建图 直接用g建图
本题在上次的基础上要输出覆盖的路径 所以used和liker数组均换成l和r两个 用get_way函数即可求出

la3415

题目要求

白书P346

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 505
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node{
	int h;
	string music,sport;
	node(int h,string music,string sport):h(h),music(music),sport(sport){}
};
vector<node>male,female;
int t,n;
int g[maxn][maxn],linker[maxn];
bool used[maxn];
bool dfs(int u){
	for(int i=1;i<=n;i++){
		if(g[u][i] && !used[i]){
			used[i]=true;
			if(linker[i]==-1 || dfs(linker[i])){
				linker[i]=u;
				return true;
			}
		}
	}
	return false;
}
int hungary(){
	int ans=0;
	mm(linker,-1);
	for(int i=1;i<=n;i++){
		mm(used,0);
		if(dfs(i)) ans++;
	}
	return ans;
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		mm(g,0);
		male.clear(),female.clear();
		for(int i=1;i<=n;i++){
			int x;
			string op,s1,s2;
			cin>>x>>op>>s1>>s2;
			if(op[0]=='M') male.push_back(node(x,s1,s2));
			else female.push_back(node(x,s1,s2));
		}
		int num1=male.size(),num2=female.size();
		for(int i=0;i<num1;i++){
			for(int j=0;j<num2;j++){
				if(abs(male[i].h-female[j].h)<=40 && male[i].music==female[j].music && male[i].sport!=female[j].sport){
					g[i+1][j+1]=1;
				}
			}
		}
		int ans=hungary();
		printf("%d\n",n-ans);
	}
	return 0;
}

思路

可以换转为二分图最大独立集
因为学生可以分成男生和女生两个集合 所以满足二分图 建图的时候要把男女分成两个集合建图
如果2个学生不满足这4个条件 说明他们不能一起去 那么在他们之间建图 表示这2个人不能同时去
最大独立集=n-最大匹配数

la 3126

题目要求

白书P357

参考AC代码(匈牙利)

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
#include<bits/stdc++.h>
#define maxn 505
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node{
	int x1,y1,x2,y2;
	int begin,end;
}a[maxn];
int g[maxn][maxn],linker[maxn];
bool used[maxn];
int t,n;
bool dfs(int u){
	for(int i=1;i<=n;i++){
		if(g[u][i] && !used[i]){
			used[i]=true;
			if(linker[i]==-1 || dfs(linker[i])){
				linker[i]=u;
				return true;
			}
		}
	}
	return false;
}
int hungary(){
	int ans=0;
	mm(linker,-1);
	for(int i=1;i<=n;i++){
		mm(used,0);
		if(dfs(i)) ans++;
	}
	return ans;
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		mm(g,0);
		for(int i=1;i<=n;i++){
			int h,m;
			scanf("%d:%d%d%d%d%d",&h,&m,&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
			a[i].begin=h*60+m;
			a[i].end=a[i].begin+abs(a[i].x1-a[i].x2)+abs(a[i].y1-a[i].y2);
		}
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				if(a[i].end+abs(a[i].x2-a[j].x1)+abs(a[i].y2-a[j].y1)<a[j].begin){
					g[i][j]=1;
				}
			}
		}
		int ans=hungary();
		printf("%d\n",n-ans);
	}
	return 0;
}

参考AC代码(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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<bits/stdc++.h>
#define maxn 1050
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int t,n;
struct node{
	int x1,y1,x2,y2;
	int begin,end;
}a[maxn];
struct Edge{
  int from, to, cap, flow;
};
struct Dinic{
	int n, m, s, t;
	vector<Edge> edges;   
	vector<int> G[maxn];   
	bool vis[maxn];         
	int d[maxn];           
	int cur[maxn];       
	void ClearAll(int n){
	    for(int i = 0; i < n; i++) G[i].clear();
	    edges.clear();
	}
	void AddEdge(int from, int to, int cap){
	    edges.push_back((Edge){from, to, cap, 0});
	    edges.push_back((Edge){to, from, 0, 0});
	    m = edges.size();
	    G[from].push_back(m-2);
	    G[to].push_back(m-1);
	}
	bool BFS(){
	    memset(vis, 0, sizeof(vis));
	    queue<int> Q;
	    Q.push(s);
	    vis[s] = 1;
	    d[s] = 0;
	    while(!Q.empty()) {
	      int x = Q.front(); Q.pop();
	      for(int i = 0; i < G[x].size(); i++) {
	        Edge& e = edges[G[x][i]];
	        if(!vis[e.to] && e.cap > e.flow) {
	          vis[e.to] = 1;
	          d[e.to] = d[x] + 1;
	          Q.push(e.to);
	        }
	      }
	    }
	    return vis[t];
	}
	int DFS(int x, int a){
	    if(x == t || a == 0) return a;
	    int flow = 0, f;
	    for(int& i = cur[x]; i < G[x].size(); i++) {
	      Edge& e = edges[G[x][i]];
	      if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > 0) {
	        e.flow += f;
	        edges[G[x][i]^1].flow -= f;
	        flow += f;
	        a -= f;
	        if(a == 0) break;
	      }
	    }
	    return flow;
	}
	int Maxflow(int s, int t){
	    this->s = s; this->t = t;
	    int flow = 0;
	    while(BFS()) {
	      memset(cur, 0, sizeof(cur));
	      flow += DFS(s, inf);
	    }
	    return flow;
	}
}g;
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		g.ClearAll(maxn);
		int S=0,T=2*n+1;
		for(int i=1;i<=n;i++){
			int h,m;
			scanf("%d:%d%d%d%d%d",&h,&m,&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
			a[i].begin=h*60+m;
			a[i].end=a[i].begin+abs(a[i].x1-a[i].x2)+abs(a[i].y1-a[i].y2);
			g.AddEdge(S,i,1);
			g.AddEdge(i+n,T,1);
		}
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				if(a[i].end+abs(a[i].x2-a[j].x1)+abs(a[i].y2-a[j].y1)<a[j].begin){
					g.AddEdge(i,j+n,1);
				}
			}
		}
		int ans=g.Maxflow(S,T);
		printf("%d\n",n-ans);
	}
	return 0;
}

思路

本题的模型是最小路径覆盖
拆点建好模型后用匈牙利和dinic求匹配均可
建图：
记录好每个点的开始时间和结束时间
如果某个点的结束时间+结束点到下一个开始点花费的时间<下一个点的开始时间 建一条边
代表至少有1分钟的等待时间

本文标题:二分图专题补

文章作者:Hippopmonkey

发布时间:2017-10-28, 12:11:52

最后更新:2017-10-29, 00:43:28

原始链接:http://xuboming8.github.io/2017/10/28/二分图专题补/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 二分图专题补
    1. 1.1. la4043
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. uva 11383
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. la3989(稳定婚姻问题)
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. uva 11419
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. la3415
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. la 3126
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码(匈牙利)
      3. 1.6.3. 参考AC代码(dinic)
      4. 1.6.4. 思路
|