网络流24题

汽车加油行驶问题

餐巾计划问题

建立两排点， 第一排每个点表示第 (i) 天的旧毛巾， 第二排每个点表示第 (i) 天的新毛巾, 新毛巾有三种来源， 旧毛巾有三种去处

• 从虚拟源点向第 (i) 天的旧毛巾连一条容量为 (r_i) 费用为 (0) 的边
• 从第 (i) 天的新毛巾向虚拟汇点连一条容量为 (r_i) 费用为 (0) 的边
• 从第 (i) 天的旧毛巾向第 (i + 1) 天的旧毛巾连一条容量为 (+infty) 费用为 (0) 的边
• 从第 (i) 天的旧毛巾向第 (i + m) 天的新毛巾连一条容量为 (+infty) 费用为 (f) 的边
• 从第 (i) 天的旧毛巾向第 (i + n) 天的新毛巾连一条容量为 (+infty) 费用为 (s) 的边
• 从虚拟源点向第 (i) 天的新毛巾连一条容量为 (+infty) 费用为 (p) 的边
  

使用计划和最大可行流一一对应， 求最小费用最大流即可

#include <bits/stdc++.h>
using namespace std;

const int N = 800 * 2 + 10;
const int M = (800 * 6 + 10) * 2;
const int INF = 1e9;

int n, p, x, xp, y, yp, S, T;
struct Edge
{
	int to, nxt, flow, w; 
}line[M];
int fist[N], idx;
int d[N], pre[N], incf[N];
bool st[N];

void add(int x, int y, int z, int w)
{
	line[idx] = {y, fist[x], z, w};
	fist[x] = idx ++;
	line[idx] = {x, fist[y], 0, -w};
	fist[y] = idx ++;
}

bool spfa()
{
	queue<int> q;
	memset(d, 0x3f, sizeof d);
	memset(incf, 0, sizeof incf);
	q.push(S), d[S] = 0, incf[S] = INF;
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		st[u] = 0;
		for(int i = fist[u]; i != -1; i = line[i].nxt)
		{
			int v = line[i].to;
			if(line[i].flow && d[v] > d[u] + line[i].w)
			{
				d[v] = d[u] + line[i].w;
				pre[v] = i;
				incf[v] = min(line[i].flow, incf[u]);
				if(!st[v])
				{
					q.push(v);
					st[v] = 1;
				}
			}
		}
	}
	return incf[T] > 0;
}

int EK()
{
	int cost = 0;
	while(spfa())
	{
		int t = incf[T];
		cost += t * d[T];
		for(int i = T; i != S; i = line[pre[i] ^ 1].to)
		{
			line[pre[i]].flow -= t;
			line[pre[i] ^ 1].flow += t;
		}
	}
	return cost;
}

int main()
{
	scanf("%d%d%d%d%d%d", &n, &p, &x, &xp, &y, &yp);
	S = 0, T = n * 2 + 1;
	memset(fist, -1, sizeof fist);
	for(int i = 1; i <= n; ++ i)
	{
		int r;
		scanf("%d", &r);
		add(S, i, r, 0);
		add(i + n, T, r, 0);
		add(S, i + n, INF, p);
		if(i < n) add(i, i + 1, INF, 0);
		if(i + x <= n) add(i, i + x + n, INF, xp);
		if(i + y <= n) add(i, i + y + n, INF, yp);
	}
	
	printf("%d
", EK());
	return 0;
}

太空飞行计划问题

当所需的器材都被选时，某实验才可被选择，该问题是一个最大权闭合子图问题

• 从源点向所有实验连一条容量为该实验收益的边
• 从所有器材向汇点连一条容量为该器材花费的边
• 从每个实验向所需的器材连一条容量为 (+infty) 的边
  

答案即为 (W(V^+)) - 最小割

#include <bits/stdc++.h>
using namespace std;

const int N = 100 + 10;
const int M = (50 * 50 + N + 10) * 2;
const int INF = 1e9;

int n, m, S, T;
struct Edge
{
	int to, nxt, flow;
}line[M];
int fist[N], idx;
int cur[N], d[N];
bool st[N];

void add(int x, int y, int z)
{
	line[idx] = {y, fist[x], z};
	fist[x] = idx ++;
	line[idx] = {x, fist[y], 0};
	fist[y] = idx ++;	
}

bool bfs()
{
	queue<int> q;
	memset(d, -1, sizeof d);
	q.push(S), d[S] = 0, cur[S] = fist[S]; 
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		for(int i = fist[u]; i != -1; i = line[i].nxt)
		{
			int v = line[i].to;
			if(d[v] == -1 && line[i].flow)
			{
				d[v] = d[u] + 1;
				cur[v] = fist[v];
				if(v == T) return 1;
				q.push(v); 
			}
		}
	}
	return 0;
}

int find(int u, int limit)
{
	if(u == T) return limit;
	int flow = 0;
	for(int i = cur[u]; i != -1 && flow < limit; i = line[i].nxt)
	{
		cur[u] = i;
		int v = line[i].to;
		if(d[v] == d[u] + 1 && line[i].flow)
		{
			int t = find(v, min(line[i].flow, limit - flow));
			if(!t) d[v] = -1;
			line[i].flow -= t;
			line[i ^ 1].flow += t;
			flow += t;
		}
	}
	return flow;
}

int dinic()
{
	int res = 0, flow;
	while(bfs()) while(flow = find(S, INF)) res += flow;
	return res;
}

void dfs(int u)
{
	st[u] = 1;
	for(int i = fist[u]; i != -1; i = line[i].nxt)
	{
		int v = line[i].to;
		if(!st[v] && line[i].flow)
			dfs(v);
	}
}

int main()
{
	scanf("%d%d", &m, &n);
	S = 0, T = m + n + 1;
	memset(fist, -1, sizeof fist);
	
	int tot = 0;
	getchar();
	for(int i = 1; i <= m; ++ i)
	{
		int w, id;
		string line;
		getline(cin, line);
		stringstream ssin(line);
		ssin >> w;
		add(S, i, w);
		while(ssin >> id) add(i, m + id, INF);
		tot += w;
	}
	for(int i = 1; i <= n; ++ i)
	{
		int p;
		scanf("%d", &p);
		add(i + m, T, p);
	}
	
	int res = dinic();
	dfs(S);
	
	for(int i = 1; i <= m; ++ i) 
		if(st[i]) printf("%d ", i); 
	puts("");
	for(int i = 1; i <= n; ++ i)
		if(st[i + m]) printf("%d ", i);
	puts("");
	printf("%d
", tot - res);
	return 0;
}

航空路线问题

最小路径覆盖问题

试题库问题

负载平衡问题

把货物当成流，仓库分为两类， 第一类的数量大于平均值， 第二类的数量小于平均值, 相邻的两个仓库之间可以运输货物

• 从源点向所有第一类仓库连一条容量为 (a_i - ar{x}) 费用为 (0) 的边
• 从所有第二类仓库向汇点连一条容量为 (ar{x} - a_i) 费用为 (0) 的边
• 从每个仓库向相邻两个仓库之间连一条容量为 (+infty) 费用为 (1) 的边
  

每个运输方案和最大可行流一一对应， 求最小费用最大流即可

#include <bits/stdc++.h>
using namespace std;

const int N = 100 + 10;
const int M = (N * 3 + 10) * 2;
const int INF = 1e9;

int n, m, S, T;
int s[N];
struct Edge
{
	int to, nxt, flow, w;
}line[M];
int fist[N], idx;
int d[N], pre[N], incf[N];
bool st[N];

void add(int x, int y, int z, int w)
{
	line[idx] = {y, fist[x], z, w};
	fist[x] = idx ++;
	line[idx] = {x, fist[y], 0, -w};
	fist[y] = idx ++; 	
}

bool spfa()
{
	queue<int> q;
	memset(d, 0x3f, sizeof d);
	memset(incf, 0, sizeof incf);
	q.push(S), d[S] = 0, incf[S] = INF;
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		st[u] = 0;
		for(int i = fist[u]; i != -1; i = line[i].nxt)
		{
			int v = line[i].to;
			if(line[i].flow && d[v] > d[u] + line[i].w)
			{
				d[v] = d[u] + line[i].w;
				pre[v] = i;
				incf[v] = min(line[i].flow, incf[u]);
				if(!st[v])
				{
					q.push(v);
					st[v] = 1;
				}
			}
		}
	}	
	return incf[T] > 0;
}

int EK()
{
	int cost = 0;
	while(spfa())	
	{
		int t = incf[T];
		cost += t * d[T];
		for(int i = T; i != S; i = line[pre[i] ^ 1].to)
		{
			line[pre[i]].flow -= t;
			line[pre[i] ^ 1].flow += t;
		}
	}
	return cost;
}

int main()
{
	scanf("%d", &n);
	S = 0, T = n + 1;
	memset(fist, -1, sizeof fist);
	int tot = 0;
	for(int i = 1; i <= n; ++ i)
	{
		scanf("%d", &s[i]);
		tot += s[i];
		add(i, i < n ? i + 1 : 1, INF, 1);
		add(i, i > 1 ? i - 1 : n, INF, 1);
	}	
	tot /= n;
	for(int i = 1; i <= n; ++ i)
		if(s[i] > tot) add(S, i, s[i] - tot, 0);
		else if(s[i] < tot) add(i, T, tot - s[i], 0);
	
	printf("%d
", EK());
	return 0;
} 

运输问题

把货物看成流，从仓库流向商店，有多个源汇点，可以建立一个虚拟源点和虚拟汇点

• 从源点向每个仓库连一条容量为 (a_i) 费用为 (0) 的边
• 从每个商店向汇点连一条容量为 (b_i) 费用为 (0) 的边
• 从每个商店向每个仓库连一条容量为 (+infty) 费用为 (c_{i,j}) 的边
  

每个运输方案和最大可行流一一对应，求最小费用最大流和最大费用最大流即可

#include <bits/stdc++.h> 
using namespace std;

const int N = 100 + 50 + 10;
const int M = (N + 100 * 50 + 10) * 2;
const int INF = 1e9;

int n, m, S, T;
struct Edge
{
	int to, nxt, flow, w;
}line[M];
int fist[N], idx;
int d[N], incf[N], pre[N];
bool st[N];

void add(int x, int y, int z, int w)
{
	line[idx] = {y, fist[x], z, w};
	fist[x] = idx ++;
	line[idx] = {x, fist[y], 0, -w};
	fist[y] = idx ++; 
}

bool spfa()
{
	queue<int> q;
	memset(d, 0x3f, sizeof d);
	memset(incf, 0, sizeof incf);
	q.push(S), d[S] = 0, incf[S] = INF;
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		st[u] = 0;
		for(int i = fist[u]; i != -1; i = line[i].nxt)
		{
			int v = line[i].to;
			if(line[i].flow && d[v] > d[u] + line[i].w)
			{
				d[v] = d[u] + line[i].w;
				pre[v] = i;
				incf[v] = min(line[i].flow, incf[u]);
				if(!st[v])
				{
					q.push(v);
					st[v] = 1; 
				} 
			}
		}
	}
	return incf[T] > 0; 
}

int EK()
{
	int cost = 0;
	while(spfa())
	{
		int t = incf[T]; 
		cost += t * d[T];
		for(int i = T; i != S; i = line[pre[i] ^ 1].to)
		{
			line[pre[i]].flow -= t;
			line[pre[i] ^ 1].flow += t;
		}
	}
	return cost;
}

int main()
{
	scanf("%d%d", &m, &n);
	S = 0, T = n + m + 1;
	memset(fist, -1, sizeof fist);
	for(int i = 1; i <= m; ++ i)
	{
		int a;
		scanf("%d", &a);
		add(S, i, a, 0);
	}
	for(int i = 1; i <= n; ++ i)
	{
		int a;
		scanf("%d", &a);
		add(i + m, T, a, 0); 
	}
	for(int i = 1; i <= m; ++ i)
		for(int j = 1; j <= n; ++ j)
		{
			int a;
			scanf("%d", &a);
			add(i, j + m, INF, a);
		}
	
	printf("%d
", EK());
	
	for(int i = 0; i < idx; i += 2)
	{
		line[i].flow += line[i ^ 1].flow;
		line[i ^ 1].flow = 0;
		line[i].w = -line[i].w;
		line[i ^ 1].w = -line[i ^ 1].w;
	}
	printf("%d
", -EK());
	
	return 0;
}

魔术球问题

最长不下降子序列问题

第一问: 用 (dp) 做一个最长不下降子序列.

第二问:

• 从源点向所有 (f(i) = 1) 的点连一条容量为 (1) 的边
• 从所有 (f(i) = s) 的点向汇点连一条容量为 (1) 的边
• 若 (f(i) = f(j) + 1), 则从 (j) 向 (i)连一条容量为 (1) 的边
• 为了保证每个点只能选择一次，把一个点拆成入点和出点， 从入点向出点连一条容量为 (1) 的边
  

第三问:
第 (1) 个点和第 (n) 个点可以用无限次
对第二问的图做如下修改：

• 第 (1) 个点和第 (n) 个点的入点到出点的边的容量设置为 (+infty)
• 从源点到第 (1) 个点的边的容量设置为 (+infty)
• 从第 (n) 个点到汇点的边(如果存在这条边)的容量设置为 (+infty)

在第二问的残留网络上继续找增广路即可
注：当 (s = 1) 的时候， 源点到汇点路径上所有边都是 (+infty)，需要特判掉

#include <bits/stdc++.h>
using namespace std;

const int N = 500 * 2 + 10;
const int M = (500 * 2 + 500 * 500 + 10) * 2;
const int INF = 1e9;

int n, S, T;
struct Edge
{
	int to, nxt, flow;
}line[M];
int fist[N], idx;
int cur[N], d[N];
int f[N], w[N];

void add(int x, int y, int z)
{
	line[idx] = {y, fist[x], z};
	fist[x] = idx ++;
	line[idx] = {x, fist[y], 0};
	fist[y] = idx ++;
} 

bool bfs()
{
	queue<int> q;
	memset(d, -1, sizeof d);
	q.push(S), d[S] = 0, cur[S] = fist[S];
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		for(int i = fist[u]; i != -1; i = line[i].nxt)
		{
			int v = line[i].to;
			if(d[v] == -1 && line[i].flow)
			{
				d[v] = d[u] + 1;
				cur[v] = fist[v];
				if(v == T) return 1;
				q.push(v); 
			}
		}
	}
	return 0;
}

int find(int u, int limit)
{
	if(u == T) return limit;
	int flow = 0;
	for(int i = cur[u]; i != -1; i = line[i].nxt)
	{
		cur[u] = i;
		int v = line[i].to;
		if(d[v] == d[u] + 1 && line[i].flow)
		{
			int t = find(v, min(line[i].flow, limit - flow));
			if(!t) d[v] = -1;
			line[i].flow -= t;
			line[i ^ 1].flow += t; 
			flow += t;
		}
	}
	return flow;
}

int dinic()
{
	int res = 0, flow;
	while(bfs()) while(flow = find(S, INF)) res += flow;
	return res;	
}

int main()
{
	scanf("%d", &n);
	S = 0, T = n * 2 + 1;
	memset(fist, -1, sizeof fist);
	
	for(int i = 1; i <= n; ++ i) scanf("%d", &w[i]);
	int s = 0;
	for(int i = 1; i <= n; ++ i)
	{
		add(i, i + n, 1);
		f[i] = 1;
		for(int j = 1; j < i; ++ j)
			if(w[j] <= w[i]) f[i] = max(f[i], f[j] + 1);
		for(int j = 1; j < i; ++ j)
			if(w[j] <= w[i] && f[i] == f[j] + 1)
				add(n + j, i, 1); 
		s = max(s, f[i]);
		if(f[i] == 1) add(S, i, 1);
	}
	for(int i = 1; i <= n; ++ i)
		if(f[i] == s) add(i + n, T, 1);
		
	printf("%d
", s);
	if(s == 1) printf("%d
%d
", n, n);
	else 
	{
		int res = dinic();
		printf("%d
", res);
		for(int i = 0; i < idx; i += 2)
		{
			int a = line[i ^ 1].to, b = line[i].to;
			if(a == S && b == 1) line[i].flow = INF;
			else if(a == n + n && b == T) line[i].flow = INF;
			else if(a == 1 && b == n + 1) line[i].flow = INF;
			else if(a == n && b == n + n) line[i].flow = INF; 
		}	
		printf("%d
", dinic() + res);
	}
	return 0;
} 

星际转移问题

最大流判定
用并查集判断 (0) 和 (n + 1) 是否连通
判断使用 (day) 天能否将所有人从 (0) 运送到 (n + 1)
利用分层图来表示天数， 点表示公交站， 边表示公交车， 人表示流量

• 从源点向第 (0) 天第 (0) 个公交站连一条容量为 (k) 的边
• 从每一天第 (n + 1) 个公交站向汇点连一条容量为 (+infty) 的边
• 每个公交站从第 (i) 天向第 (i + 1)天连一条容量为 (+infty) 的边
• 按照公交车的移动路线和天数连接容量为该公交车最大承载量的边

枚举天数，每次在原有网络后面新加一排点，可直接在原有网络的残留网络上继续找增广路， 比二分效率更高

#include <bits/stdc++.h>
using namespace std;

const int N = 751 * 15 + 10;
const int M = (N + 750 + 20 * 751 + 10) * 2;
const int INF = 1e9; 

int n, m, k, S, T;
struct Edge
{
	int to, nxt, flow;
}line[M];
int fist[N], idx;
int cur[N], d[N];
struct Ship
{
	int h, r, id[30];
}ships[30];
int fa[30];

int find(int x)
{
	if(fa[x] != x) fa[x] = find(fa[x]);
	return fa[x];
}

int get(int i, int day)
{
	return day * (n + 2) + i;	
}

void add(int x, int y, int z)
{
	line[idx] = {y, fist[x], z};
	fist[x] = idx ++;
	line[idx] = {x, fist[y], 0};
	fist[y] = idx ++;
}

bool bfs()
{
	queue<int> q;
	memset(d, -1, sizeof d);
	q.push(S), d[S] = 0, cur[S] = fist[S];
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		for(int i = fist[u]; i != -1; i = line[i].nxt)
		{
			int v = line[i].to;
			if(d[v] == -1 && line[i].flow)
			{
				d[v] = d[u] + 1;
				cur[v] = fist[v];
				if(v == T) return 1;
				q.push(v);
			}
		}
	}	
	return 0;
} 

int find(int u, int limit)
{
	if(u == T) return limit;
	int flow = 0;
	for(int i = cur[u]; i != -1 && flow < limit; i = line[i].nxt)
	{
		cur[u] = i;
		int v = line[i].to;
		if(d[v] == d[u] + 1 && line[i].flow)
		{
			int t = find(v, min(line[i].flow, limit - flow));
			if(!t) d[v] = -1;
			line[i].flow -= t;
			line[i ^ 1].flow += t;
			flow += t;
		}
	}
	return flow;
}

int dinic()
{
	int res = 0, flow;
	while(bfs()) while(flow = find(S, INF)) res += flow;
	return res;	
}

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	S = N - 2, T = N - 1;
	memset(fist, -1, sizeof fist);
	for(int i = 0; i < 30; ++ i) fa[i] = i;
	for(int i = 0; i < m; ++ i)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		ships[i] = {a, b};
		for(int j = 0; j < b; ++ j)
		{
			int id;
			scanf("%d", &id);
			if(id == -1) id = n + 1; 
			ships[i].id[j] = id;
			if(j) 
			{
				int x = ships[i].id[j - 1];
				fa[find(x)] = find(id);
			}
		}
	}
	if(find(0) != find(n + 1)) puts("0");
	else
	{
		add(S, get(0, 0), k);
		add(get(n + 1, 0), T, INF);
		int day = 1, res = 0;
		while(1)
		{
			add(get(n + 1, day), T, INF);
			for(int i = 0; i <= n + 1; ++ i)
				add(get(i, day - 1), get(i, day), INF);
			for(int i = 0; i < m; ++ i)
			{
				int r = ships[i].r;
				int a = ships[i].id[(day - 1) % r];
				int b = ships[i].id[day % r];
				add(get(a, day - 1), get(b, day), ships[i].h);
			} 
			res += dinic();
			if(res >= k) break;
			++ day;
		}
		printf("%d
", day);
	}
	return 0;
}

方格取数问题

飞行员配对方案问题

二分图最大匹配
(O(msqrt n))

• 从源点向第一个点集每个点连一条容量为(1)的边
• 从第二个点集每个点向汇点连一条容量为(1)的边
• 两个点集之间可以配对的点连一条容量为(1)的边
  

#include <bits/stdc++.h>
using namespace std;

const int N = 200 + 10;
const int M = 5200 + 10;
const int INF = 1e9;

int n, m, S, T;
struct Edge
{
	int to, nxt, flow;
}line[M];
int fist[N], idx;
int cur[N], d[N];

void add(int x, int y, int z)
{
	line[idx] = {y, fist[x], z};
	fist[x] = idx ++;
	line[idx] = {x, fist[y], 0};
	fist[y] = idx ++; 
}

bool bfs()
{
	queue<int> q;
	memset(d, -1, sizeof d);
	q.push(S), d[S] = 0, cur[S] = fist[S]; 
	while(!q.empty())
	{ 
		int u = q.front(); q.pop();
		for(int i = fist[u]; i != -1; i = line[i].nxt)
		{
			int v = line[i].to;
			if(d[v] == -1 && line[i].flow)
			{
				d[v] = d[u] + 1;
				cur[v] = fist[v];
				if(v == T) return 1;
				q.push(v); 
			} 
		}
	}
	return 0;
}

int find(int u, int limit)
{
	if(u == T) return limit;
	int flow = 0;
	for(int i = cur[u]; i != -1 && flow < limit; i = line[i].nxt)
	{
		cur[u] = i;
		int v = line[i].to;
		if(d[v] == d[u] + 1 && line[i].flow)
		{
			int t = find(v, min(line[i].flow, limit - flow));
			if(!t) d[v] = -1;
			line[i].flow -= t;
			line[i ^ 1].flow += t;
			flow += t;
		} 
	}
	return flow;
}

int dinic()
{
	int res = 0, flow;
	while(bfs()) while(flow = find(S, INF)) res += flow;
	return res;	
}

int main()
{
	scanf("%d%d", &m, &n);
	memset(fist, -1, sizeof fist);
	S = 0, T = n + 1;
	for(int i = 1; i <= m; ++ i) add(S, i, 1);
	for(int i = m + 1; i <= n; ++ i) add(i, T, 1);
	int a, b;
	while(scanf("%d%d", &a, &b) == 2)
	{
		if(a == -1 && b == -1) break;
		add(a, b, 1);
	}
	printf("%d
", dinic());
	
	for(int i = 0; i < idx; i += 2)
	{
		int u = line[i ^ 1].to, v = line[i].to;
		if(v > m && v <= n && !line[i].flow)
			printf("%d %d
", u, v);
	}
	return 0;
} 

骑士共存问题

如果两个位置放置骑士可以相互攻击到， 则这两个位置之间连一条边
定义横纵坐标之和为偶数的点为偶点， 横纵坐标之和为奇数的点为奇点， 边一定在偶点和奇点之间， 所以该图是一个二分图
则该问题转化为最大点权独立集问题， 点权为 (1)

• 从源点向所有偶点连一条容量为 (1) 的边
• 从所有奇点向汇点连一条容量为 (1) 的边
• 相互攻击到的点之间连一条容量为 (+infty) 的边
  

答案为 总点权和 - 最小点权覆盖集

#include <bits/stdc++.h>
using namespace std;

const int N = 40000 + 10;
const int M = (N + 20000 * 8 + 10) * 2;
const int INF = 1e9;
const int dx[] = {2, -2, 2, -2, 1, -1, 1, -1};
const int dy[] = {1, 1, -1, -1, 2, 2, -2, -2}; 

int n, m, S, T;
struct Edge
{
	int to, nxt, flow;
}line[M];
int fist[N], idx;
int cur[N], d[N];
bool g[220][220];

void add(int x, int y, int z)
{
	line[idx] = {y, fist[x], z};
	fist[x] = idx ++;
	line[idx] = {x, fist[y], 0};
	fist[y] = idx ++;
}

bool bfs()
{
	queue<int> q;
	memset(d, -1, sizeof d);
	q.push(S), d[S] = 0, cur[S] = fist[S];
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		for(int i = fist[u]; i != -1; i = line[i].nxt)
		{
			int v = line[i].to;
			if(d[v] == -1 && line[i].flow)
			{
				d[v] = d[u] + 1;
				cur[v] = fist[v];
				if(v == T) return 1;
				q.push(v);
			}
		}
	} 
	return 0;
}

int find(int u, int limit)
{
	if(u == T) return limit;
	int flow = 0;
	for(int i = cur[u]; i != -1 && flow < limit; i = line[i].nxt)
	{
		cur[u] = i;
		int v = line[i].to;
		if(d[v] == d[u] + 1 && line[i].flow)
		{
			int t = find(v, min(line[i].flow, limit - flow));
			if(!t) d[v] = -1;
			line[i].flow -= t;
			line[i ^ 1].flow += t;
			flow += t;
		}
	}
	return flow;
} 

int dinic()
{
	int res = 0, flow;
	while(bfs()) while(flow = find(S, INF)) res += flow;
	return res;
}

int get(int x, int y)
{
	return (x - 1) * n + y;
}

int main()
{
	scanf("%d%d", &n, &m);
	S = 0, T = n * n + 1;
	memset(fist, -1, sizeof fist);
	for(int i = 1; i <= m; ++ i)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		g[a][b] = 1;
	}
	int tot = 0;
	for(int i = 1; i <= n; ++ i)
		for(int j = 1; j <= n; ++ j)
		{
			if(g[i][j]) continue;
			if(i + j & 1) 
			{
				add(S, get(i, j), 1);
				for(int k = 0; k < 8; ++ k)
				{
					int x = i + dx[k], y = j + dy[k];
					if(x >= 1 && x <= n && y >= 1 && y <= n && !g[x][y])
						add(get(i, j), get(x, y), INF);
				}
			}	
			else add(get(i, j), T, 1);
			tot ++;
		}
	printf("%d
", tot - dinic());
	return 0;
}

最长k可重线段集问题

最长k可重区间集问题

圆桌问题

二分图多重匹配
找一个满流的方案,看一下最大流是否满流即可

• 第一个点集每个点向第二个点集每个点连一条容量为(1)的边
• 从源点向第一个点集每个点连一条容量为(r_i)的边
• 从第二个点集每个点向汇点连一条容量为(c_i)的边
  

#include <bits/stdc++.h>
using namespace std;

const int N = 420 + 10;
const int M = (150 * 270 + N) * 2;
const int INF = 1e9;

int n, m, S, T;
struct Edge
{
	int to, nxt, flow;
}line[M];
int fist[N], idx;
int cur[N], d[N];
int r[N], c[N];

void add(int x, int y, int z)
{
	line[idx] = {y, fist[x], z};
	fist[x] = idx ++;
	line[idx] = {x, fist[y], 0};
	fist[y] = idx ++;
}

bool bfs()
{
	queue<int> q;
	memset(d, -1, sizeof d);
	q.push(S), d[S] = 0, cur[S] = fist[S];
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		for(int i = fist[u]; i != -1; i = line[i].nxt)
		{
			int v = line[i].to;
			if(d[v] == -1 && line[i].flow)
			{
				d[v] = d[u] + 1;
				cur[v] = fist[v];
				if(v == T) return 1;
				q.push(v);
			}
		} 
	} 
	return 0;
}

int find(int u, int limit)
{
	if(u == T) return limit;
	int flow = 0;
	for(int i = cur[u]; i != -1 && flow < limit; i = line[i].nxt)
	{
		cur[u] = i;
		int v = line[i].to;
		if(d[v] == d[u] + 1 && line[i].flow)
		{
			int t = find(v, min(line[i].flow, limit - flow));
			if(!t) d[v] = -1;
			line[i].flow -= t;
			line[i ^ 1].flow += t;
			flow += t;
		} 
	}
	return flow;
}

int dinic()
{
	int res = 0, flow;
	while(bfs()) while(flow = find(S, INF)) res += flow;
	return res;	
} 

int main()
{
	scanf("%d%d", &m, &n);
	memset(fist, -1, sizeof fist);
	S = 0, T = n + m + 1;
	int tot = 0;
	for(int i = 1; i <= m; ++ i) 
	{
		int r;
		scanf("%d", &r);
		add(S, i, r);
		tot += r; 
	}
	for(int i = 1; i <= n; ++ i) 
	{
		int c;
		scanf("%d", &c);
		add(i + m, T, c);
	}
	for(int i = 1; i <= m; ++ i)
		for(int j = 1; j <= n; ++ j)
			add(i, j + m, 1); 
			
	if(dinic() != tot) puts("0");
	else 
	{
		puts("1");
		for(int i = 1; i <= m; ++ i)
		{
			for(int j = fist[i]; j != -1; j = line[j].nxt)
			{
				int v = line[j].to;
				if(v > m && v <= n + m && !line[j].flow) 
					printf("%d ", v - m);
			}
			puts("");
		}
	}
	return 0;
} 

数字梯形问题

当路径互不相交时，每个点和边都只能选择一次, 限制在边和点上，对于边上的限制可以直接加到容量上，对于点上的限制考虑拆点， 费用在点上， 加在出点和入点的边上

• 从每个点的入点到出点连一条容量为 (1) 费用为点权的边
• 从当前点到下一层可到达的点连一条容量为 (1) 费用为 (0) 的边
• 从虚拟源点向第一层每个点连一条容量为 (1) 费用为 (0) 的边
• 从最后一层每个点向虚拟汇点连一条容量为 (1) 费用为 (0) 的边
  

当可以在节点处相交时，只对边有限制，把点的限制放开即可，即每个点从入点到出点的流量设为 (+infty)，同时最后一层点到虚拟汇点的边的容量限制也要放开

当允许在结点相交或边相交时，对边和点都没有限制，把边的限制也放开即可，即边的容量设置为 (+infty)

每种路径方案和最大可行流一一对应，求最大费用最大流即可

#include <bits/stdc++.h>
using namespace std;

const int N = 600 * 2 + 10;
const int M = (600 + 20 + 39 + 600 * 2 + 10) * 2;
const int INF = 1e9;

int n, m, S, T;
struct Edge
{
	int to, nxt, flow, w;
}line[M];
int fist[N], idx;
int d[N], pre[N], incf[N];
bool st[N];
int id[40][40], g[40][40];

void add(int x, int y, int z, int w)
{
	line[idx] = {y, fist[x], z, w};
	fist[x] = idx ++;
	line[idx] = {x, fist[y], 0, -w};
	fist[y] = idx ++;	
}

bool spfa()
{
	queue<int> q;
	memset(d, -0x3f, sizeof d);
	memset(incf, 0, sizeof incf);
	q.push(S), d[S] = 0, incf[S] = INF;
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		st[u] = 0;
		for(int i = fist[u]; i != -1; i = line[i].nxt)
		{
			int v = line[i].to;
			if(line[i].flow && d[v] < d[u] + line[i].w)
			{
				d[v] = d[u] + line[i].w;
				pre[v] = i;
				incf[v] = min(line[i].flow, incf[u]);
				if(!st[v])
				{
					q.push(v);
					st[v] = 1;
				}
			}
		} 
	} 
	return incf[T] > 0;
}

int EK()
{
	int cost = 0;
	while(spfa())
	{
		int t = incf[T];
		cost += t * d[T];
		for(int i = T; i != S; i = line[pre[i] ^ 1].to)
		{
			line[pre[i]].flow -= t;
			line[pre[i] ^ 1].flow += t;
		}
	}
	return cost;
}

int main()
{
	int cnt = 0;
	scanf("%d%d", &m, &n);
	S = ++ cnt; T = ++ cnt;
	for(int i = 1; i <= n; ++ i)
		for(int j = 1; j <= m + i - 1; ++ j)
		{
			scanf("%d", &g[i][j]);
			id[i][j] = ++ cnt;
		}	
	//
	memset(fist, -1, sizeof fist); idx = 0;
	for(int i = 1; i <= n; ++ i)
		for(int j = 1; j <= m + i - 1; ++ j)
		{
			add(id[i][j] * 2, id[i][j] * 2 + 1, 1, g[i][j]);
			if(i == 1) add(S, id[i][j] * 2, 1, 0);
			if(i == n) add(id[i][j] * 2 + 1, T, 1, 0);
			if(i < n) 
			{
				add(id[i][j] * 2 + 1, id[i + 1][j] * 2, 1, 0);
				add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, 1, 0);
			}
		}
	printf("%d
", EK());
	//
	memset(fist, -1, sizeof fist); idx = 0;
	for(int i = 1; i <= n; ++ i)
		for(int j = 1; j <= m + i - 1; ++ j)
		{
			add(id[i][j] * 2, id[i][j] * 2 + 1, INF, g[i][j]);
			if(i == 1) add(S, id[i][j] * 2, 1, 0);
			if(i == n) add(id[i][j] * 2 + 1, T, INF, 0);
			if(i < n) 
			{
				add(id[i][j] * 2 + 1, id[i + 1][j] * 2, 1, 0);
				add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, 1, 0);
			}
		}
	printf("%d
", EK());
	//
	memset(fist, -1, sizeof fist); idx = 0;
	for(int i = 1; i <= n; ++ i)
		for(int j = 1; j <= m + i - 1; ++ j)
		{
			add(id[i][j] * 2, id[i][j] * 2 + 1, INF, g[i][j]);
			if(i == 1) add(S, id[i][j] * 2, 1, 0);
			if(i == n) add(id[i][j] * 2 + 1, T, INF, 0);
			if(i < n) 
			{
				add(id[i][j] * 2 + 1, id[i + 1][j] * 2, INF, 0);
				add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, INF, 0);
			}
		}
	printf("%d
", EK());
	
	return 0;
} 

深海机器人问题

网格图费用流
费用在边上，不需要拆点，但是费用只能取一次，所以两个点之间要建两种边

• 从虚拟源点向每个起点连一条容量为 (a_i) 费用为 (0) 的边
• 从每个终点向虚拟汇点连一条容量为 (b_i) 费用为 (0) 的边
• 可到达的点之间连一条容量为 (1) 费用为 (c_i) 的边
• 可到达的点之间连一条容量为 (+infty) 费用为 (0) 的边
  

方案和最大可行流一一对应， 求最大费用最大流即可

#include <bits/stdc++.h>
using namespace std;

const int N = 16 * 16 + 10;
const int M = (N * 2 * 2 + 4 + 6 + 10) * 2;
const int INF = 1e9;

int n, m, S, T;
struct Edge
{
	int to, nxt, flow, w;
}line[M];
int fist[N], idx;
int d[N], pre[N], incf[N];
bool st[N];

void add(int x, int y, int z, int w)
{
	line[idx] = {y, fist[x], z, w};
	fist[x] = idx ++;
	line[idx] = {x, fist[y], 0, -w};
	fist[y] = idx ++;
}

bool spfa()
{
	queue<int> q;
	memset(d, -0x3f, sizeof d);
	memset(incf, 0, sizeof incf);
	q.push(S), d[S] = 0, incf[S] = INF;
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		st[u] = 0;
		for(int i = fist[u]; i != -1; i = line[i].nxt)
		{
			int v = line[i].to;
			if(line[i].flow && d[v] < d[u] + line[i].w)
			{
				d[v] = d[u] + line[i].w;
				pre[v] = i;
				incf[v] = min(line[i].flow, incf[u]);
				if(!st[v])
				{
					q.push(v);
					st[v] = 1;
				}
			}
		}
	}
	return incf[T] > 0;
}

int EK()
{
	int cost = 0;
	while(spfa())
	{
		int t = incf[T];
		cost += t * d[T];
		for(int i = T; i != S; i = line[pre[i] ^ 1].to)
		{
			line[pre[i]].flow -= t;
			line[pre[i] ^ 1].flow += t;
		}
	}
	return cost;
}

int get(int x, int y)
{
	return x * (m + 1) + y;
}
 
int main()
{
	int A, B;
	scanf("%d%d%d%d", &A, &B, &n, &m);
	S = (n + 1) * (m + 1), T = S + 1;
	memset(fist, -1, sizeof fist);
	for(int i = 0; i <= n; ++ i)
		for(int j = 0; j < m; ++ j)	
		{
			int c;
			scanf("%d", &c);
			add(get(i, j), get(i, j + 1), 1, c);
			add(get(i, j), get(i, j + 1), INF, 0);
		} 
	for(int i = 0; i <= m; ++ i)
		for(int j = 0; j < n; ++ j)
		{
			int c;
			scanf("%d", &c);
			add(get(j, i), get(j + 1, i), 1, c);
			add(get(j, i), get(j + 1, i), INF, 0);
		}
	for(int i = 1; i <= A; ++ i)
	{
		int k, x, y;
		scanf("%d%d%d", &k, &x, &y);
		add(S, get(x, y), k, 0);
	}
	for(int i = 1; i <= B; ++ i)
	{
		int r, x, y;
		scanf("%d%d%d", &r, &x, &y);
		add(get(x, y), T, r, 0);
	}
	printf("%d
", EK());
	return 0;
} 

软件补丁问题

火星探险问题

分配问题

二分图最优匹配问题， 与二分图匹配的建图方式类似， 建立虚拟源点和虚拟汇点

• 从源点向每个工作连一条容量为 (1) 费用为 (0) 的边
• 从每个工人向汇点连一条容量为 (1) 费用为 (0) 的边
• 从每个工作向每个工人连一条容量为 (1) 费用为 (c_{i,j}) 的边
  

最大可行流和分配方案一一对应， 求最小费用最大流和最大费用最大流即可

#include <bits/stdc++.h>
using namespace std;

const int N = 100 + 10;
const int M = (50 * 50 + N + 10) * 2;
const int INF = 1e9;

int n, m, S, T;
struct Edge
{
	int to, nxt, flow, w;
}line[M];
int fist[N], idx;
int d[N], pre[N], incf[N];
bool st[N];

void add(int x, int y, int z, int w)
{
	line[idx] = {y, fist[x], z, w};
	fist[x] = idx ++;
	line[idx] = {x, fist[y], 0, -w};
	fist[y] = idx ++;
}

bool spfa()
{
	queue<int> q;
	memset(d, 0x3f, sizeof d);
	memset(incf, 0, sizeof incf);
	q.push(S), d[S] = 0, incf[S] = INF;  
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		st[u] = 0;
		for(int i = fist[u]; i != -1; i = line[i].nxt)
		{
			int v = line[i].to;
			if(line[i].flow && d[v] > d[u] + line[i].w)
			{
				d[v] = d[u] + line[i].w;
				pre[v] = i;
				incf[v] = min(line[i].flow, incf[u]);
				if(!st[v])
				{
					q.push(v);
					st[v] = 1;
				}
			}
		}
	}
	return incf[T] > 0;
}

int EK()
{
	int cost = 0;
	while(spfa())
	{
		int t = incf[T];
		cost += t * d[T];
		for(int i = T; i != S; i = line[pre[i] ^ 1].to)
		{
			line[pre[i]].flow -= t;
			line[pre[i] ^ 1].flow += t;
		}
	}
	return cost;
}

int main()
{
	scanf("%d", &n);
	S = 0, T = n * 2 + 1;
	memset(fist, -1, sizeof fist);
	for(int i = 1; i <= n; ++ i)
	{
		add(S, i, 1, 0);
		add(i + n, T, 1, 0);
	}
	for(int i = 1; i <= n; ++ i)
		for(int j = 1; j <= n; ++ j)
		{
			int c;
			scanf("%d", &c);
			add(i, j + n, 1, c);
		}
	
	printf("%d
", EK());
	for(int i = 0; i < idx; i += 2)
	{
		line[i].flow += line[i ^ 1].flow;
		line[i ^ 1].flow = 0;
		line[i].w = -line[i].w;
		line[i ^ 1].w = -line[i ^ 1].w;
	}
	printf("%d
", -EK());
	return 0;
} 

机器人路径规划问题

孤岛营救问题