每日总结-1月14日

acm 图论
2021ACM寒假集训
发布日期:   2022-01-14
文章字数:   3.2k

图论进阶

网络流

  • 最大流
  • 最小费用最大流

今日战况

Standing

前言

感觉今天的主题，挺难的，上午听课的时候也是没有跟上节奏，然后又去反复看课件和查找资料，才把最大流差不多理解，最小费用最大流就留给明天了

部分题目

A题: Drainage Ditches

题目传送门

题目

Every time it rains on Farmer John’s fields, a pond forms over Bessie’s favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie’s clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch.
Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network.
Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.

Input

The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch.

Output

For each case, output a single integer, the maximum rate at which water may emptied from the pond.

Sample Input

1
2
3
4
5
6
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10

Sample Output

1
50
题目大意

有个排水系统，有 n 条单向通道和 m 个位置，问从位置 1 到位置 m 的最大流速是多大。

思路

是一道很典型的最大流模板题，通过单向通道进行建图，之后进行一遍 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
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#define Inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
const int MAXX=205;
const double eps=0.0000001;

struct rode{
	int st,en,flow,cap;
};
vector<rode> ro;
vector<int> to[MAXX];
int n,m;
int cur[MAXX],d[MAXX];
bool vis[MAXX];

inline void add(int st,int en,int cap){
	rode re;int si=ro.size();
	re.st=st;re.en=en;re.flow=0;re.cap=cap;
	ro.push_back(re);to[st].push_back(si);
	re.st=en;re.en=st;re.flow=0;re.cap=0;
	ro.push_back(re);to[en].push_back(si+1);
}

bool bfs(int st,int en){
	memset(vis,0,sizeof(vis));
	queue<int> qq;
	qq.push(st);
	d[st]=0;vis[st]=true;
	while(!qq.empty()){
		int jj=qq.front();qq.pop();
		int si=to[jj].size();
		for(int i=0;i<si;++i){
			rode kk=ro[to[jj][i]];
			if(!vis[kk.en]&&(kk.cap-kk.flow)>0){
				vis[kk.en]=true;
				d[kk.en]=d[jj]+1;
				qq.push(kk.en);
			}
		}
	}
	
	return vis[en];
}

int dfs(int now,int en,int flow){
	if(now==en||flow==0) return flow;
	int re=0,f=0,si=to[now].size();
	for(int& i=cur[now];i<si;++i){
		rode& jj=ro[to[now][i]];
		if(d[jj.en]==d[jj.st]+1){
			f=dfs(jj.en,en,min(flow,jj.cap-jj.flow));
			if(f){
				jj.flow+=f;
				ro[to[now][i]^1].flow-=f;
				re+=f;
				flow-=f;
				if(flow==0) break;
			}
		}
	}
	return re;
}

int dinic(int st,int en){
	int re=0;
	while(bfs(st,en)){
		memset(cur,0,sizeof(cur));
		re+=dfs(st,en,Inf);
	}
	return re;
}

void solve_it(){
	for(int i=1;i<=m;++i){
		int st,en,cap;
		scanf("%d%d%d",&st,&en,&cap);
		add(st,en,cap);
	}
	
	printf("%d\n",dinic(1,n));
	
	ro.clear();
	for(int i=1;i<=n;++i)
		to[i].clear();
}

int main(){
//	int t;scanf("%d",&t);
//	while(t--)
	while(~scanf("%d%d",&m,&n))
		solve_it();
	
	return 0;
}

C题: 假期的宿舍

题目传送门

题目

学校放假了······有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。比如A和B都是学校的学生，A要回家，而C来看B，C与A不认识。我们假设每个人只能睡和自己直接认识的人的床。那么一个解决方案就是B睡A的床而C睡B的床。而实际情况可能非常复杂，有的人可能认识好多在校学生，在校学生之间也不一定都互相认识。我们已知一共有n个人，并且知道其中每个人是不是本校学生，也知道每个本校学生是否回家。问是否存在一个方案使得所有不回家的本校学生和来看他们的其他人都有地方住。

输入格式

第一行一个数T表示数据组数。接下来T组数据，每组数据第一行一个数n表示涉及到的总人数。接下来一行n个数，第i个数表示第i个人是否是在校学生(0表示不是，1表示是)。再接下来一行n个数，第i个数表示第i个人是否回家(0表示不回家，1表示回家，注意如果第i个人不是在校学生，那么这个位置上的数是一个随机的数，你应该在读入以后忽略它)。接下来n行每行n个数，第i行第j个数表示i和j是否认识(1表示认识，0表示不认识，第i行i个的值为0，但是显然自己还是可以睡自己的床)，认识的关系是相互的。1 ≤ n ≤ 50,1 ≤ T ≤ 20

输出格式

对于每组数据，如果存在一个方案则输出“^_^”(不含引号)否则输出“T_T”(不含引号)。(注意输出的都是半角字符，即三个符号的ASCII码分别为94,84,95)

Sample Input

1
2
3
4
5
6
7
8
9
10
11
1
3
1 1 0

0 1 0

0 1 1

1 0 0

1 0 0

Output

1
^_^
题目大意

学校放假了……有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。

比如 A 和 B 都是学校的学生，A 要回家，而 C 来看B，C 与 A 不认识。我们假设每个人只能睡和自己直

接认识的人的床。那么一个解决方案就是 B 睡 A 的床而 C 睡 B 的床。而实际情况可能非常复杂，有的

人可能认识好多在校学生，在校学生之间也不一定都互相认识。

我们已知一共有 n个人，并且知道其中每个人是不是本校学生，也知道每个本校学生是否回家。问是否

存在一个方案使得所有不回家的本校学生和来看他们的其他人都有地方住。

思路

典型的二分图最大匹配问题，可以用最大流进行求解，主要就是建图，先创造出一个原点和汇点，接着原点连接人，汇点连接床，人和床之间再连接，只有直接认识的人才能睡到朋友床上，接着进行一次最大流即可。

代码
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#define Inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
const int MAXX=205;
const double eps=0.0000001;

struct rode{
	int st,en,flow,cap;
};
vector<rode> ro;
vector<int> to[MAXX];
int n,m;
int cur[MAXX],d[MAXX];
bool vis[MAXX],isStu[MAXX];

inline void add(int st,int en,int cap){
	rode re;int si=ro.size();
	re.st=st;re.en=en;re.flow=0;re.cap=cap;
	ro.push_back(re);to[st].push_back(si);
	re.st=en;re.en=st;re.flow=0;re.cap=0;
	ro.push_back(re);to[en].push_back(si+1);
}

bool bfs(int st,int en){
	memset(vis,0,sizeof(vis));
	queue<int> qq;
	qq.push(st);
	d[st]=0;vis[st]=true;
	while(!qq.empty()){
		int jj=qq.front();qq.pop();
		int si=to[jj].size();
		for(int i=0;i<si;++i){
			rode kk=ro[to[jj][i]];
			if(!vis[kk.en]&&(kk.cap-kk.flow)>0){
				vis[kk.en]=true;
				d[kk.en]=d[jj]+1;
				qq.push(kk.en);
			}
		}
	}
	
	return vis[en];
}

int dfs(int now,int en,int flow){
	if(now==en||flow==0) return flow;
	int re=0,f=0,si=to[now].size();
	for(int& i=cur[now];i<si;++i){
		rode& jj=ro[to[now][i]];
		if(d[jj.en]==d[jj.st]+1){
			f=dfs(jj.en,en,min(flow,jj.cap-jj.flow));
			if(f){
				jj.flow+=f;
				ro[to[now][i]^1].flow-=f;
				re+=f;
				flow-=f;
				if(flow==0) break;
			}
		}
	}
	return re;
}

int dinic(int st,int en){
	int re=0;
	while(bfs(st,en)){
		memset(cur,0,sizeof(cur));
		re+=dfs(st,en,Inf);
	}
	return re;
}

void solve_it(){
	scanf("%d",&n);
	int en=2*n+1,num=n;
	for(int i=1;i<=n;++i){
		int jj;scanf("%d",&jj);
		if(jj){
			isStu[i]=true;
			add(i,n+i,1);
			add(n+i,en,1);
		}
	}
	for(int i=1;i<=n;++i){
		int jj;scanf("%d",&jj);
		if(isStu[i]&&jj==0)
			add(0,i,1);
		else if(!isStu[i])
			add(0,i,1);
		else if(isStu[i]&&jj==1)
			--num;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			int jj;scanf("%d",&jj);
			if(jj&&isStu[j]){
				add(i,j+n,1);
			}
		}
	}
	
	if(dinic(0,en)>=num)
		printf("%c%c%c\n",94,95,94);
	else
		printf("%c%c%c\n",84,95,84);
	
	ro.clear();
	for(int i=0;i<MAXX;++i){
		to[i].clear();
		isStu[i]=false;
	}
}

int main(){
	int t;scanf("%d",&t);
	while(t--)
		solve_it();
	
	return 0;
}

E题: 飞行员配对

题目传送门

题目

第二次世界大战时期，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2名飞行员，其中1名是英国飞行员，另1名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空 军一次能派出最多的飞机 。对于给定的外籍飞行员与英国飞行员的配合情况，编程找出一个最佳飞行员配对方案， 使皇家空军一次能派出最多的飞机。

Input

第1行有2个正整数 m 和 n。n 是皇家空军的飞行 员总数(n<100);m 是外籍飞行员数。外籍飞行员编号为 1m;英国飞行员编号为 m+1n。接下来每行有 2 个正整数 i 和 j，表示外籍飞行员 i 可以和英国飞行员 j 配合。输入最后以 2 个-1 结束。

Output

第 1 行是最佳飞行 员配对方案一次能派出的最多的飞机数 M。如果所求的最佳飞行员配对方案不存在，则输出‘No Solution!’。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -1

Sample Output

1
4
题目大意

看题吧，都是中文

思路

构建一个二分图，左边是外籍飞行员，右边是英国飞行员，接着把能够进行配合的飞行员进行连接，在左边构建一个原点，连接所有外籍飞行员，在右边构建一个汇点，连接所有英国飞行员。接着进行一次最大流即可。

代码
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
103
104
105
106
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#define Inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
const int MAXX=205;
const double eps=0.0000001;

struct rode{
	int st,en,flow,cap;
};
vector<rode> ro;
vector<int> to[MAXX];
int n,m;
int cur[MAXX],d[MAXX];
bool vis[MAXX];

inline void add(int st,int en,int cap){
	rode re;int si=ro.size();
	re.st=st;re.en=en;re.flow=0;re.cap=cap;
	ro.push_back(re);to[st].push_back(si);
	re.st=en;re.en=st;re.flow=0;re.cap=0;
	ro.push_back(re);to[en].push_back(si+1);
}

bool bfs(int st,int en){
	memset(vis,0,sizeof(vis));
	queue<int> qq;
	qq.push(st);
	d[st]=0;vis[st]=true;
	while(!qq.empty()){
		int jj=qq.front();qq.pop();
		int si=to[jj].size();
		for(int i=0;i<si;++i){
			rode kk=ro[to[jj][i]];
			if(!vis[kk.en]&&(kk.cap-kk.flow)>0){
				vis[kk.en]=true;
				d[kk.en]=d[jj]+1;
				qq.push(kk.en);
			}
		}
	}
	
	return vis[en];
}

int dfs(int now,int en,int flow){
	if(now==en||flow==0) return flow;
	int re=0,f=0,si=to[now].size();
	for(int& i=cur[now];i<si;++i){
		rode& jj=ro[to[now][i]];
		if(d[jj.en]==d[jj.st]+1){
			f=dfs(jj.en,en,min(flow,jj.cap-jj.flow));
			if(f){
				jj.flow+=f;
				ro[to[now][i]^1].flow-=f;
				re+=f;
				flow-=f;
				if(flow==0) break;
			}
		}
	}
	return re;
}

int dinic(int st,int en){
	int re=0;
	while(bfs(st,en)){
		memset(cur,0,sizeof(cur));
		re+=dfs(st,en,Inf);
	}
	return re;
}

void solve_it(){
	scanf("%d%d",&m,&n);
	int n1=n+1;
	int jj,kk;
	while(~scanf("%d%d",&jj,&kk)){
		if(jj==-1) break;
		add(jj,kk,1);
	}
	for(int i=1;i<=m;++i)
		add(0,i,1);
	for(int i=m+1;i<=n;++i)
		add(i,n1,1);
	
	int ans=dinic(0,n1);
	if(ans)
		printf("%d\n",ans);
	else
		printf("No Solution!\n");
}

int main(){
//	int t;scanf("%d",&t);
//	while(t--)
		solve_it();
	
	return 0;
}

总结

这一部分难度比较大，进行了一天的练习，也算是差不多理解了，但是练习还是太少，并不能熟练运用，仍需多加练习，明天进行最小费用最大流。

文章作者: Shaun
文章链接: http://shaun-2314.github.io/2022/01/14/1-14/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Shaun !
acm 图论
评论
  目录