网络流 学习笔记

最大流

略。

update：我发现我的最大流一直是写错的！！写错一年了！！这一年居然没有被卡真是奇迹……

void Dedge(int sta,int edn,lon w){
	ecnt++;
	e[ecnt]=(dino){edn,fst[sta],w};
	fst[sta]=ecnt;
}

void edge(int sta,int edn,lon w){
	Dedge(sta,edn,w),Dedge(edn,sta,0);
}

bool bfs(){
	memset(dep,0,sizeof dep);
	head=1,tail=1,que[1]=ds;
	dep[ds]=1,fstz[ds]=fst[ds];
	while(head<=tail){
		int o=que[head];head++;
		mar(o){
			if(dep[v]||!e[E].w)continue;
			dep[v]=dep[o]+1,fstz[v]=fst[v];
			if(v==dt)return 1;
			tail++,que[tail]=v;
		}
	}
	return 0;
}

lon dfs(int o,lon val){
	if(o==dt)return val;
	lon res=val;
	marz(o){
		if(!res)break;
		fstz[o]=E;
		if( dep[v]!=dep[o]+1 || !e[E].w )continue;
		lon out=dfs(v, min(e[E].w,res) );
		if(!out){dep[v]=0;continue;}
		e[E].w-=out,e[E^1].w+=out;
		res-=out;
	}
	return val-res;
}

lon dinic(){
	lon tot=0;
	while( bfs() )tot+=dfs(ds,inf);
	return tot;
}

费用流

略。

无源汇上下界可行流

问题

你有一个图，现在边 \(i\) 的流量必须在 \([l_i,r_i]\)，合法的方案是每个点的入流等于其出流，求是否有一种方案？

解法

约定： \(a>b:c\) 代表 \(a\) 向 \(b\) 连一条流量上限为 \(c\) 的有向边。

首先我们给每个边流上 \(l_i\)，这样每个边的范围就是 \([0,r_i-l_i]\) 了。

但是这样可能会有一些点入流大于出流（过剩），有一些入流小于出流（不够）。

过剩的点需要流出，我们便让它的出边继续流。

注：以 LOJ 模板题样例 2 为说明对象。

这是每个边的范围 \([0,r_i-l_i]\) 中 \((r_i-l_i)\) 的值（不是图的流量）：

1

比如 2 号点，它的入流是 2，出流是 1。我们要让它再流出 1 的流量。

但是这是图的流量：

2

显然都是 0，因为根本就没有人给它流量！

而我们想到，源点和汇点是可以 提供 / 吸收 流量的。

于是我们就加上一个虚拟源点 S。连一条边， \(S>2:1\) ，其中那个 \(1\) 就是其入度与出度的差。

3

这样就可以流动了：

4

如果把一开始减去的 \(l_i\) 加上，就是这样的了：

5

2 号点的入流等于出流成立。

所以流程：

  1. 使每一条原来的边 \(a>b\) 变成从 \([l_i,r_i]\) 变成 \([0,r_i-l_i]\)，同时 \(a\) 的出流加上 \(l_i\)，\(b\) 的入流加上 \(l_i\)。
  2. 令 \(x\) 为一个点入流减去出流的绝对值。让所有入流大于出流的点（过剩的点），连边 \(S>i:x\) ；让出流大于入流的点（不足的点）连边 \(i>T:x\)。
  3. 跑最大流。
  4. 如果不等于……突然不想写了不知道怎么回事（写句子写一半停下来鸽，不愧是我）

相关

标签