算法学习

dinic

待补

最小费用最大流spfa

待补

isap

待补

模板是天

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef pair<int,int> pii;
const int N = 2005;
const int inf = 0x3f3f3f3f;

struct edge
{
	int u,v,cap;
	edge(int u,int v,int cap):u(u),v(v),cap(cap){}
};

vector<edge> es;
vector<int> G[N];

int dis[N];
int cur[N];

int S,T;

void adde(int u,int v,int cap)
{
	es.push_back(edge(u,v,cap));
	es.push_back(edge(v,u,0));
	int m = es.size();
	G[u].push_back(m-2);
	G[v].push_back(m-1);
}

bool bfs()
{
	for (int i = S;i <= T;i++) dis[i] = inf;
	dis[S] = 0;
	queue<int> q;
	q.push(S);
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		for (int i = 0;i < G[u].size();i++)
		{
			edge &e = es[G[u][i]];
			int v = e.v;
			if (e.cap > 0 && dis[v] >= inf)
			{
				dis[v] = dis[u] + 1;
				q.push(v);
			}
		}
	}
	return dis[T] < inf;
}

int dfs(int u,int mxflow)
{
	if (u == T) return mxflow;
	for (int i = cur[u];i < G[u].size();i++)
	{
		cur[u] = i;
		edge &e = es[G[u][i]];
		int v = e.v;
		if (e.cap > 0 && dis[v] == dis[u] + 1)
		{
			int flow = dfs(v,min(mxflow,e.cap));
			if (flow)
			{
				e.cap -= flow;
				es[G[u][i]^1].cap += flow;
				return flow;
			}
		}
	}
	return 0;
}

int dinic()
{
	int ans = 0;
	while (bfs())
	{
		int flow = 0;
		memset(cur,0,sizeof(cur));
		while (flow = dfs(S,inf)) ans += flow;
	}
	return ans;
}

最小费用最大流 spfa

 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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
const int N = 505;
const int inf = 0x3f3f3f3f;

struct edge
{
	int u,v,c,f,cost;
	edge(){}
	edge(int u,int v,int c,int f,int cost):u(u),v(v),c(c),f(f),cost(cost){}
};

vector<edge> es;
vector<int> G[N];

int a[N];
int rev[N];//用于记录反向边
int dis[N];
bool vis[N];
int S,T;

void init()
{
	for (int i = S;i <= T;i++) G[i].clear();
	es.clear();
}

void adde(int u,int v,int c,int cost)
{
	es.push_back(edge(u,v,c,0,cost));
	es.push_back(edge(v,u,0,0,-cost));
	int m = es.size();
	G[u].push_back(m-2);
	G[v].push_back(m-1);
}

bool spfa(int &flow,int &cost)
{
	for (int i = S;i <= T;i++) dis[i] = inf;
	memset(vis,0,sizeof(vis));
	dis[S] = 0;vis[S] = 1;
	rev[S] = 0;a[S] = inf;
	queue<int> q;
	q.push(S);
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for (int i = 0;i < G[u].size();i++)
		{
			edge &e = es[G[u][i]];
			int v = e.v;
			if (e.c > e.f && dis[v] > dis[u] + e.cost)
			{
				dis[v] = dis[u] + e.cost;
				rev[v] = G[u][i];
				a[v] = min(a[u],e.c - e.f);
				if (!vis[v])
				{
					vis[v] = 1;
					q.push(v);
				} 
			}
		}
	}
	if (dis[T] >= inf) return false;
	flow += a[T];
	cost += dis[T] * a[T];
	for (int u = T;u != S;u = es[rev[u]].u)
	{
		es[rev[u]].f += a[T];
		es[rev[u]^1].f -= a[T];
	}
	
	return true;
}

int mcmf()
{
	int cost = 0;
	int flow = 0;
	while (spfa(flow,cost));
	return cost;
}

isap

这里要记一下$dis[S] = n$。这个$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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;

struct edge
{
	int u,v,cap;
	edge(){}
	edge(int u,int v,int cap):u(u),v(v),cap(cap){}
};

vector<int> G[N];
vector<edge> es;
int dis[N],cur[N];
int gap[N];
int S,T;
int n,m;

void adde(int u,int v,int cap)
{
	es.push_back(edge(u,v,cap));
	es.push_back(edge(v,u,cap));
	int sz = es.size();
	G[u].push_back(sz-2);
	G[v].push_back(sz-1);
}

void bfs()
{
	for (int i = 0;i <= n;i++) dis[i] = inf;
	dis[T] = 0;
	gap[0] = 1;
	queue<int> q;
	q.push(T);
	while (!q.empty())
	{
		int u = q.front();q.pop();
		for (int i = 0;i < G[u].size();i++)
		{
			edge &e = es[G[u][i]];
			int v = e.v;
			if (dis[v] == inf)
			{
				dis[v] = dis[u] + 1;
				gap[dis[v]]++;
				q.push(v);
			}
		}
	}
}

int isap(int u,int f)
{
	if (u == T) return f;
	int res = f;
	for (int i = 0;i < G[u].size();i++)
	{
		edge &e = es[G[u][i]];
		int v = e.v;
		if (e.cap > 0 && dis[u] == dis[v] + 1)
		{
			int flow = isap(v,min(res,e.cap));
			res -= flow;
			e.cap -= flow;
			es[G[u][i]^1].cap += flow;
			if (!res) return f;
		}
	} 
	if (!(--gap[dis[u]])) dis[S] = n;
	gap[++dis[u]]++;
	return f - res;
}

int maxflow()
{
	bfs();
	int ans = 0;
	while (dis[S] < n) ans += isap(S,inf); 
	return ans;
}

解题记录

最大流

1.Dining poj 3281

题意: 约翰有若干头牛,每头牛都有自己喜欢吃的东西和喜欢喝的饮料。每种东西和每种饮料的数量都为1,且只能被独占。问最多有多少头牛同时享受到自己喜欢的东西和饮料。

题解: 建图很巧妙,首先把饮料连边到牛,然后把牛连边到东西,容量都为1。一开始wa了几发,因为经验浅薄,不知道把牛拆点限制容量。不把牛拆点的话,容易出现,牛1占有东西1和饮料1,牛1又占有了东西2和饮料2,所以把牛拆点,容量设置为1。然后跑一遍dinic就ok。

2.ACM Computer Factory poj 3436

题意: 有一个流水线生产电脑,流水线由若干台机器构成。每台机器的参数是每小时输出的电脑数量,输入描述以及输出描述。输入描述由p个数字构成,包括0,1,2:0表示这个零件不能出现,1表示这个零件必须出现,2表示这个零件无所谓;输出描述由p个数字组成,包括0,1:0表示没有这个零件,1表示有这个零件。现在重新安排机器的顺序,使得每小时生产的完整的电脑数量最大,并且输出流水线的构成。

题解: 首先用输入描述和输出描述连边,机器同样拆点,连边为每小时生产数量限制流量,跑dinic。流水线的构成,就是记录最大流的路径,我的思路是在结构体中加入一个org,表示origin原始的流量,最后找哪些正向边的原始流量和现有流量不相同,差值就是两台机器之间的流量。如果一条正向边有流量,那么一定是对最大流有贡献的。

3.A Plug for UNIX poj 1087

题意: 有设备,插座,适配器三种东西,前两种数量有限,第三种数量无限。适配器之间是可以无限次连接的,只要端口适配。问最少有多少个设备无法接上插座。

题解: 很裸的最大流,设备与插座连边,设备与适配器连边,适配器与适配器连边,适配器与插座连边,插座与汇点连边。需要注意的地方是输入的第二部分和第三部分中出现的接口可能在插座中都没有。然后点数设置大一点,1000都RE,2000就A了。直接用dinic跑就行了。

4.Power Network poj 1459

题意:

有生产者,消费者和分发者三个类别。生产者只能生产,消费者只能消费。三者都能分发。问整个网络最多消费多少。

题解:

看了题解

裸的多源多汇最大流。正常做法是超级源点连接生产者,权值为最多生产量。消费者连接超级汇点,权值为最大消耗量。然后跑最大流。蓝儿我的做法就很智障,把每个点都拆成了2个点,造成debug2小时惨案,告诉我不是每个图都要拆点的。记录案发现场:

上面的WA了,下面的A了。为什么呢?因为其它的生产者也是可以连接到另一个生产者的,所以如果把一个生产者的内部流量限制了,那就会造成从这个生产者流出的流量只是自己生产的。

5.Food hdu 4292

题意:

食堂有若干种食物和若干种饮料,每个学生有喜好的饮料和食物,问最多能服务多少个学生。

题解:

这不是跟约翰的牛一样吗?食物连学生,学生拆点连饮料,跑最大流。其实还有个trick:

You should notice that, when one’s requirement is unmet, he/she would just go away, refusing any service.

暗示允许退流,所以就用网络流(雾

6.Control hdu 4289

题意:

有一伙人要搞事情,从一个地方跑到另一个地方,你要阻止他们,所以要选择一个点集放警卫,使得所有人不论怎么走都至少经过这个点集中的一个点。放警卫是要花钱的,所以计算费用最小。

题解:

看了题解

带权最小点割集。求最小割嘛,就是求最大流。但是是求点的最小割,怎么办?拆点,点与点之间连边,边权就是费用,然后跑最大流即可。

7.Island Transport hdu 4280

题意:

一群岛屿,有些岛屿之间有双向道路,问每小时从最西边岛屿到最东边岛屿的客流量。

题解:

看了题解

最大流,一开始用dinic TLE到怀疑人生,然后查题解说是isap裸题,遂学习isap,然后成功AC。数据量还是有点大,T为10,$n,m$最大都是$10^5$。注意这是无向图的流,所以建图的时候,要么加2次边,要么一次,但是正反都有容量。

8.Leapin’ Lizards hdu 2732

题意:

一个迷宫当中有很多柱子,有些柱子上有蜥蜴。每当一个蜥蜴跳出一个柱子(跳到柱子上对柱子没有影响),柱子的持久度减1,为0的时候柱子就会崩塌。曼哈顿距离小于一定值的时候,就可以跳跃。迷宫边缘的柱子里出口的距离为1,问最后最少有多少只蜥蜴不能出去。

题解:

柱子拆点,相互之间曼哈顿距离满足条件可以连边。源点向有蜥蜴的点连边,可以跳到出口的柱子向汇点连边。跑最大流,蜥蜴总数减去这个最大流就是答案,但是输出略坑,不仅名次注意单复数,are和is也要注意单复数。

9.Sabotage uva 10480

题意:

求最小割的边割集。

题解:

看了题解

通过这个题目学习,跑了最大流之后,点集会分为源点集合和汇点集合。设跑完最大流之后,源点到每一个点的最大流为f,那么当$f > 0$,这个点就属于源点集合,否则属于汇点集合。如果一条边同时连不属于同一个集合的两个点,那么这条边就是边割集当中的一条边。方案就是跑完最大流之后再BFS一次,标记出源点集合和汇点集合。

10.Escape hdu 3605

题意:

有$n$个人,$m$个星球。每个人有适配的星球,星球也有容量。问最后是否每个人都能住到星球上。

题解:

看了题解

由于$1 <= n <= 10^5,1 <= m <= 10$,一开始最大流跑就TLE了,因为点太多了。考虑到m比较小,所以人的种类最多就1024种,状态压缩,就把问题解决了。还是比较巧妙的。

11.Marriage Match II hdu 3081

题意:

改变的稳定婚姻问题。每个女孩在找到自己心仪的男孩之后,再重新开始找,并且每一个女生在每一轮的心仪男孩都得不一样。问最多可以进行多少轮。

题解:

搜了网上题目的做法都是并查集+二分+最大流。其实我的做法并不是这样。我的做法就是每次设置流为1,然后跑最大流,直到无法增广为止。具体的做法就是每次源点和汇点加边,跑完最大流之后再把边给删掉,然后再次加边。。。只不过因为脑子糊涂一开始没用并查集所以debug了很久。

12.Marriage Match IV hdu 3416

题意:

简化问题,就是问有多少条没有交集的最短路(最短路当中包含的边没有交集,且最短路长度相同)。

题解:

看了题解

一开始向着费用流的方向去想了,因为涉及到最短路。所以就首先求出最短路,然后求当$dis[T] <= mi$的最大流,mi表示最短路,这样就保证了流的路径都最短路。但是TLE了很久。去搜了题解,居然是求最大流,但是其中的边都是最短路上的边。那么如何找最短路上的边呢,就正向建边跑起点最短路,为$d1[N]$,然后反向建边跑重点最短路,为$d2[N]$,然后遍历原输入的每一条边,为$u,v,cost$,如果满足$d1[u] + d2[v] + cost == d1[en]$,那么这一条边就是最短路当中的边,将其加入网络流的图中,最后跑最大流即可。

13.Frequency Hopping uva 11248

题意:

问可否改变一条边的容量使得最大流大于某个值,并且求出边的可选方案。

题解:

直接枚举所有的边显然是不行的,复杂度过不去。首先求出最大流,然后求出割边。枚举每条割边增大流量即可。一开始用dinicT了,然后加了当前弧优化,就A了。

最小费用最大流

1.Going Home poj 2195

题意: 给一张地图,有$N$个人和$N$个房子,要让每个人走到房子当中,并且每个房子只能容纳一个人。人走到相邻的一个花费为1。问让所有人都走到房子的最小总费用。

题解: 算出每个人到每个房子的哈密顿距离,作为边的费用。房子拆点,因为要保证只有一个人住进来,房子与房子之间的边的容量设置为1。最后跑一遍最小费用最大流就可以了。

加边都能写错我是真的沙碧,案发现场记录一下

1
2
3
4
5
6
7
8
void adde(int u,int v,int c,int cost)
{
	es.push_back(edge(u,v,c,0,cost));
	es.push_back(edge(u,v,0,0,-cost));
	int m = es.size();
	G[u].push_back(m-2);
	G[v].push_back(m-1);
}

2.Minimum Cost poj 2516

题意:

有m个公司,每个公司都提供k种货物;有n个客户,对k种货物有不同的需求。不同公司的不同货物送到不同的客户需要不同的费用,问是否能满足每个客户的需求,去最小的运送费用。

题解:

看了题解

一开始思路是对了,就是把每个公司的每种货物和每个客户的每种货物都拆点连边,但是这样建图的话,图的规模太大了,所以TLE了。应该每种货物单独计算最大流和费用流,这样图的规模很小,所以能过。又犯了一个愚蠢的错误。输出没结束就break掉了,又导致了若干小时的debug时间。

3.Dijkstra, Dijkstra. uva 10806

题意:

暗示不能用最短路解(。从起点到终点选出边集没有交集的两条路径,并且使得它们的长度之和最短。

题解:

看了题解

其实一开始想对了,但是后面又想多了。卡住的地方是因为无向图,所以想是否可以一条边被走两次,即正着被走一次,反着被走一次,后来再一想,这不就是退流了嘛,这条边就相当于没走。然后,源点到1连容量为2的边,终点到汇点连容量为2的边,跑费用流,看最后最大流是否为2即可。最短是行不通的,第一次最短+第二次最短不一定小于第一次次短+第二次次短。这题揭露了流量可以反悔的本质。