Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

网络流常见方法汇总

发布于：2019年10月11日

 

 次浏览

一年半前为了省选学网络流之后第一次做网络流的题

首先是自己改造后的Dinic:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>
#define INF 2147483647
#define MAXN 10005
#define MAXM 100005
using namespace std;
struct addedge
{
	int to,flow,cap,ne;
}e[MAXM << 1];
int head[MAXN];
int cur[MAXN];
int dep[MAXN];
int ecnt = -1;
int N,M,S,T;
void init()
{
	memset(head,-1,sizeof head);
	memset(dep,0,sizeof dep);
	return ;
}
void addedge(int u,int v,int cap)
{
	e[++ecnt].to = v;
	e[ecnt].flow = 0;
	e[ecnt].cap = cap;
	e[ecnt].ne = head[u];
	head[u] = ecnt;
	return ;
}
queue<int> q;
int bfs()
{
	memset(dep,0,sizeof dep);
	dep[S] = 1;
	q.push(S);
	while(!q.empty())
	{
		int nown = q.front();
		q.pop();
		for(int i = head[nown];i != -1;i = e[i].ne)
		{
			int to = e[i].to;
			if(dep[to] != 0 || e[i].flow >= e[i].cap) continue;
			dep[to] = dep[nown] + 1;
			q.push(to);
		}
	}
	return dep[T];
}
int homin(int a,int b)
{
	if(a < b) return a;
	return b;
}
int dfs(int x,int fl)
{
	if(x == T) return fl;
	for(int &i = cur[x]; i != -1;i = e[i].ne)
	{
		int to = e[i].to;
		if(dep[to] != dep[x] + 1 || e[i].flow >= e[i].cap) continue;
		int f = dfs(to,homin(fl,e[i].cap - e[i].flow));
		if(f > 0)
		{
			e[i].flow += f;
			e[i^1].flow -= f;
			return f;
		}
	}
	return 0;
}
int Dinic()
{
	int ans = 0;
	while(bfs())
	{
		memcpy(cur,head,sizeof cur);
		while(int d = dfs(S,INF)) ans += d;
	}
	return ans;
}
void read(int &ss)
{
	ss=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') ss*=10,ss+=ch-'0',ch=getchar();return ;
}
int main()
{
	init();
	cin >> N >> M >> S >> T;
	for(int i = 0;i < M;i++)
	{
		int tu,tv,tw;
		cin >> tu >> tv >> tw;
		addedge(tu,tv,tw);
		addedge(tv,tu,0);
	}
	cout << Dinic() << endl;
}

就用网络流24题当例题了

最大流

P2766 最长不下降子序列问题

第一问直接n^2就行,dp后的数组记为f,其中f[i]代表以第i个数结尾的最长不下降子序列的长度,答案记为ans1. a[i]代表第i个数.

第二问可以给对于每个 ,如果 并且 ,就意味着选完第j个数后,再选第i个数,可以选到一个最长的不下降子序列.

因为最后是要记录最长不下降子序列的个数,所以每个最长不下降子序列对答案的贡献均为1,所以可以从j到i连一条容量为1的边. 因为所有 的点a都可作为起点,所有 的点b都可作为终点,所以可以用超级源向所有满足条件的点a连一条边,所有满足条件的点b向超级汇连一条边.同理,这些边容量均为1.

这样对整个图跑一个最大流即可得到答案.但是为了保证每个数只被用一次,需要利用拆点限制每个点的流量为1.即将一个点拆为两个点,并且这两个点之间仅有一条容量为1的边.

第三问只是取消了 和 的使用次数限制,所以只要把限制这两个点使用次数的边的容量全部改为INF即可,即超级源向 的边, 到超级汇的边, 和 分别拆成的两点之间的边这四条边的容量限制改为INF后再跑最大流即可.

超级汇有一种整合所有信息的感觉,将所有和答案直接相关的节点流量信息全部汇总起来.

对于点流量的限定,一般用拆点的方法.拆点可以用*2-1和*2防止撞车.

图可以表示元素之间的关系,这题元素之间的关系十分明显(走过一个节点下一个可以走哪些节点),考虑建图.

第二问是一种"并列"的问题,取出的几个子序列地位相同,且均满足相同的条件.网络流解决的也是这种"并列"的问题,在图中,每一个节点,每一条路径都是地位相同的.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#define INF 2147483647
#define MAXN 550
#define osu(a,b,i) for(int i = (a);i <= (b);i++)
#define nso(a,b,i) for(int i = (a);i >= (b);i--)
#define lovelive long long int
using namespace std;
inline int homin(int a,int b)
{
	if(a > b) return b;
	return a;
}
struct Edge{
	int to,cap,flow,ne;
};
Edge e[MAXN << 2];
Edge e2[MAXN << 2];
int dep[MAXN << 1];
int cur[MAXN << 1];
int head[MAXN << 1];
int ecnt = -1;
int S,T;
int N;
int a[MAXN];
queue <int> q;
void init()
{
	memset(e,0,sizeof e);
	memset(head,-1,sizeof head);
	memset(dep,0,sizeof dep);
}
int addedge(int u,int v)
{
	e[++ecnt].to = v;
	e[ecnt].cap = 1;
	e[ecnt].flow = 0;
	e[ecnt].ne = head[u];
	head[u] = ecnt;
	e[++ecnt].to = u;
	e[ecnt].cap = 0;
	e[ecnt].flow = 0;
	e[ecnt].ne = head[v];
	head[v] = ecnt;
	return ecnt - 1;
}
int bfs()
{
	queue<int> q2;
	swap(q,q2);
	memset(dep,0,sizeof dep);

	q.push(S);
	dep[S] = 1;
	//cout << S << "dd" <<q.front()<< endl;
	while(!q.empty())
	{
		int nown = q.front();
		//cout << nown << "}" << endl;
		q.pop();
		for(int i = head[nown];i!=-1;i = e[i].ne)
		{
			//cout << e[i].to << "gs" << dep[e[i].to]<<endl;
			int to = e[i].to;
			if(dep[to] != 0 || e[i].flow >= e[i].cap) continue;
			//cout << "!" << endl;
			dep[to] = dep[nown] + 1;
			q.push(to);
		}
	}
	return dep[T];
}
int dfs(int x,int fl)
{
	if(x == T) return fl;
	for(int &i = cur[x];i != -1;i = e[i].ne)
	{
		int to = e[i].to;
		if(dep[to] != dep[x]+1 || e[i].flow >= e[i].cap) continue;
		int f = dfs(to,homin(fl,e[i].cap - e[i].flow));
		if(f > 0)
		{
			e[i].flow += f;
			e[i^1].flow -= f;
			return f;
		}
	}
	return 0;
}
int Dinic()
{
	int flow = 0;
	//cout << "!" << endl;
	while(bfs())
	{
		//cout << "!" << endl;
		memcpy(cur,head,sizeof cur);
		while(int d = dfs(S,INF)) flow += d;
		//cout << "?" << endl;
	}
	return flow;
}
int f[MAXN];
int fdp()
{
	int ans = -1;
	for(int i = 1;i <= N;i++)
	{
		int maxx = 0;
		for(int j = 1;j < i;j++)
		{
			if(f[j] > maxx && a[j] <= a[i])
			{
				maxx = f[j];
			}
		}
		f[i] = maxx + 1;
		if(f[i] > ans) ans = f[i];
	}
	return ans;
}
int main()
{
	init();
	cin >> N;
	for(int i = 1;i <= N;i++)
	{
		cin >> a[i];
	}
	int ans1 = fdp();
	S = 0;T = 2*N+1;
	int ea,eb,ec,ed;
	for(int i = 1;i <= N;i++)
	{
		if(i == 1)
		{
			ec = addedge(2*i-1,2*i);
		}else if(i == N)
		{
			ed = addedge(2*i-1,2*i);
		}else{
			addedge(2*i-1,2*i);
		}
		if(f[i] == 1)
		{
			if(i == 1)
			{
				ea = addedge(S,2*i-1);
			}else{
				addedge(S,2*i-1);
			}
		}
		if(f[i] == ans1)
		{
			if(i == N)
			{
				eb = addedge(2*i,T);
			}else{
				addedge(2*i,T);
			}
		}
		for(int j = 1;j < i;j++)
		{
			if(f[i] == f[j] + 1 && a[i] >= a[j])
			{
				addedge(2*j,2*i-1);
			}
		}
	}
	memcpy(e2,e,sizeof e);
	cout << ans1 << endl;
	cout << Dinic() << endl;
	cout << ea << " " << eb << " " << ec << " " << ed << endl;
	//cout << ":1" << endl;
	memcpy(e,e2,sizeof e);
	//cout << ":2" << endl;
	if(ea >= 0 && ea <= ecnt) e[ea].cap = INF;
	if(eb >= 0 && eb <= ecnt) e[eb].cap = INF;
	if(ec >= 0 && ec <= ecnt) e[ec].cap = INF;
	if(ed >= 0 && ed <= ecnt) e[ed].cap = INF;
	//cout << ":3" << endl;
	if(N == 1)
	{
		cout << 1 << endl;
	}
	else{
		cout << Dinic() << endl;
	}
}

最小割

P2774 方格取数问题

这道题也是一中"并列"的问题,要所有元素地位均相同,需要从中挑选出几个.

"割"的概念是,让这个图的原点无法到达汇点,意味着关系的断绝.

将这个方格棋盘染色后,就是让黑点和其相邻的白点不能同时出现.

只要让建立的图反映出,当黑点和相邻的白点同时出现时,源点和汇点就会联通,这样让图不连通就意味着没有黑点和相邻白点同时出现.

为了让删去的点值最小,要把点值反映到边权上,才能利用"最小"割求解

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>
#define INF 2147483647
#define MAXN 10005
#define MAXM 100005
using namespace std;
struct addedge
{
	int to,flow,cap,ne;
}e[MAXM << 1];
int head[MAXN];
int cur[MAXN];
int dep[MAXN];
int ecnt = -1;
int N,M,S,T;
void init()
{
	memset(head,-1,sizeof head);
	memset(dep,0,sizeof dep);
	return ;
}
void addedge(int u,int v,int cap)
{
	e[++ecnt].to = v;
	e[ecnt].flow = 0;
	e[ecnt].cap = cap;
	e[ecnt].ne = head[u];
	head[u] = ecnt;
	return ;
}
queue<int> q;
int bfs()
{
	memset(dep,0,sizeof dep);
	dep[S] = 1;
	q.push(S);
	while(!q.empty())
	{
		int nown = q.front();
		q.pop();
		for(int i = head[nown];i != -1;i = e[i].ne)
		{
			int to = e[i].to;
			if(dep[to] != 0 || e[i].flow >= e[i].cap) continue;
			dep[to] = dep[nown] + 1;
			q.push(to);
		}
	}
	return dep[T];
}
int homin(int a,int b)
{
	if(a < b) return a;
	return b;
}
int dfs(int x,int fl)
{
	if(x == T) return fl;
	for(int &i = cur[x]; i != -1;i = e[i].ne)
	{
		int to = e[i].to;
		if(dep[to] != dep[x] + 1 || e[i].flow >= e[i].cap) continue;
		int f = dfs(to,homin(fl,e[i].cap - e[i].flow));
		if(f > 0)
		{
			e[i].flow += f;
			e[i^1].flow -= f;
			return f;
		}
	}
	return 0;
}
int Dinic()
{
	int ans = 0;
	while(bfs())
	{
		memcpy(cur,head,sizeof cur);
		while(int d = dfs(S,INF)) ans += d;
	}
	return ans;
}
int a[105][105];
int main()
{
	init();
	cin >> M >> N;
	S = N*M;
	T = N*M+1;
	int sum = 0;
	for(int i = 1;i <= M;i++)
	{
		for(int j = 1;j <= N;j++)
		{
			cin >> a[i][j];
			sum += a[i][j];
		}
	}
	for(int i = 1;i <= M;i++)
	{
		for(int j = 1;j <= N;j++)
		{
			int num = (i-1)*N + j-1;
			if((i+j) % 2 == 1)
			{
				addedge(S,num,a[i][j]);
				addedge(num,S,0);
				if(i > 1)
				{
					addedge(num,num-N,INF);
					addedge(num-N,num,0);
				}
				if(i < M)
				{
					addedge(num,num+N,INF);
					addedge(num+N,num,0);
				}
				if(j < N)
				{
					addedge(num,num+1,INF);
					addedge(num+1,num,0);
				}
				if(j > 1)
				{
					addedge(num,num-1,INF);
					addedge(num-1,num,0);
				}
			}else{
				addedge(num,T,a[i][j]);
				addedge(T,num,0);
			}
		}
	}
	cout << sum - Dinic() << endl;
	return 0;
}

To be continued...

网络流常见方法汇总
https://blog.honoka.tech/2019/10/11/网络流常见方法汇总/
Post author
Orange Cheers
Posted on
2019年10月11日
Update
2024年10月30日
License
CC BY-NC-SA 4.0
署名-非商业性使用-相同方式共享 4.0 国际。

更新于：2024年10月30日

图论

算法总结

网络流

评论