【网络流】模板小结

前言：

花了一礼拜学了网络流，最小割及费用流，估计还要再花半个月把整个网络流彻彻底底地过一遍。

这篇博文先记一下学网络流全家桶中各代码的一些总体思路&细节，再挑十几道题讲讲如何正确建图（可能还不够）。

现在是$19/03/07$，时间不够，今晚就总结下几个板子吧。。

网络流入门

1. 概念啥的别类比水流，太抽象，类比人流会好理解一些（认真）

2. 引入新的概念：增广路。和二分图来回走交替路不同，网络流的增广路就是一条最大容量>实际流量的路径，找出所有增广路之后就可以得到最大流。

为啥是严格大于的呢，因为如果实际容量已经等于最大容量了，就相当于你这时候已经再也挤不下人了，如果你还认为可以加0个人就会死循环， $if (!v[u]$&&$w)$ 的$w$就体现这一点（意思是仍有容量）。。

3. 对于每次增广路的处理就类似二分图了，核心思想都在于反悔，只不过二分图是递归回去找错误，EK是把错误以反向边的形式记录下来，要是想反悔直接送您回家

反向边虽然是我们脑补出来的，但是也是要一开始建在图里面，实打实参加求增广路过程的。。
反向边w初值为0，在EK算法中关于正常边反着操作就行了。

$1.~EK$算法：

1. 找增广路实质上还是BFS暴力搜索的过程（要注意的都在代码里注释了）：

   if (!v[u]&&w) {//没访问过+还有流量=走着
   		p[u].pp=k,p[u].ed=i;
   		if (u==t) return 1;  //流到终点就是增广路！ 
   		v[u]=1; q.push(u); 
   }

2. 找完增广路我们也顺手把路径存下来了，然后依然是暴力走增广路的操作：

①先暴力走一遍增广路找最小流量

②再暴力修改所有增广路边权和反向边边权

③答案加上。

for (int i=t;i!=s;i=p[i].pp) mw=min(mw,e[p[i].ed].w);
//找这条路的最小流量，减掉！ 
for (int i=t;i!=s;i=p[i].pp){
	int ed=p[i].ed;
	e[ed].w-=mw,e[ed+1].w+=mw;
}  
//从终点倒回去找前驱，反向边的处理 
ans+=mw;

EK部分代码务必要在5分钟内打完+正确，切忌将时间浪费在这上面!！

#include <iostream>//26-->30
#include <cstring>
#include <queue>
#include <climits>
using namespace std;

struct ed{
	int u,next,w;
}e[300000];
struct path{
	int pre,ed;
}p[300000];
int n,m,s,t,x,y,w,st=1,fir[100000];
queue<int> q; bool v[100000];
void add(int u,int v,int w){
	e[++st].u=v; e[st].next=fir[u]; e[fir[u]=st].w=w;
}


bool bfs()
{
	memset(v,0,sizeof(v)); memset(p,0,sizeof(p));
	while (!q.empty()) q.pop(); q.push(s);
	while (!q.empty())
	{
		int k=q.front(); q.pop();
		for (int i=fir[k];i;i=e[i].next)
		{
			int u=e[i].u,w=e[i].w;
			if (!v[u]&&w) {
				p[u].pre=k; p[u].ed=i;
				if (u==t) return 1;
				v[u]=1,q.push(u);	
			}
		}
	}
	return 0;
}

int ek(){
	int ans=0;
	while (bfs())
	{
		int mw=10000000;
		for (int i=t;i!=s;i=p[i].pre) mw=min(mw,e[p[i].ed].w);
		for (int i=t;i!=s;i=p[i].pre)
		{
			int ed=p[i].ed;
			e[ed].w-=mw; e[ed^1].w+=mw;	
		}
		ans+=mw;   //ans加上当前增广路的最大流量 
	}
	return ans;
}

int main()
{
	cin>>n>>m>>s>>t;
	for (int i=1;i<=m;i++) {
		cin>>x>>y>>w; add(x,y,w); add(y,x,0);
	}
	cout<<ek()<<endl;
}d

$2.~Dinic$算法

$1.~ $概念：

EK每次搜到一条增广路就要重新bfs下，太慢啦！

我们要搞一个可以一次多条增广路一起更新的算法，于是就又发明了dinic。

$2.~ $核心思想：

引入分层图的概念，把不同点到起点的最短距离用BFS求出，然后用DFS每次都找当前深度+1的点，往下推进，回溯的时候就顺便更新所有增广路上的点。

$BFS,DFS的时候依然要遵循有流量再走的原则（说白了就还要判$w>0$），是否访问到改成判断最小深度，将访问的v数组挪到里面处理入队列之类的问题。。

最后通过判断终点深度是否是INF，来确定是否还有增广路。

DFS每次找到深度加一的点后，递归应该这样写：

int mw=0;
if (p==n) return now;
...
if (w&&d[u]==d[p]+1){  //这里也要判断流量，不然死循 
if (mw=dfs(u,min(now,w))) {
	e[i].w-=mw,e[i^1].w+=mw;
	return mw;    
    //找着增广路了，直接回【就太慢了】。 
}

now是递归里上一次的最大流量，但发现这依然是DFS一下BFS一下，还是慢。。

$3.~$Dinic优化：

于是就有了多路增广优化！

1. 核心思想：只要我当前点流出的流量小于我的最大流入流量，我就能一直找增广路！

设一个变量used表示当前节点已经用了多少流量，那么只要加一行就会极大优化时间：

if (w&&d[u]==d[p]+1){  //这里也要判断流量，不然死循 
	if (mw=dfs(u,min(now-used,w))) {
    //由于当前流量已经用了一点，不在是最大流量了，所以要更新。
	e[i].w-=mw,e[i^1].w+=mw;
	used+=mw; if (used==now) break;
	//找着增广路了，直接回【就太慢了】。 
	}
}

其实已经挺快了，但是那些人闲着无聊又发明了弧优化。

1. 核心思想：当我们增广完一条边，退出这条边递归后，这条边就没有利用价值了，因为它所经过的增广路径已经被榨干了。。

于是我们就搞一个c数组来代替fir数组，直接从上一个没有被榨干的边再走，之前那些边就跳过了。

如图，比方说先走s->3->t，那么3->t这边就废了，当我们再从s->1->3时候，我们就直接到3->5，不管t了。。

写出来大概是：

• BFS里面 $memcpy(c,fir,sizeof(fir));$
• DFS:

  for (int i=c[p];i;i=e[i].next)
  	{
  		c[p]=i;
  		....

大概就这样？？

代码依然保证不超过6~7分钟打完加正确：

#include <iostream>//43-->46
#include <cstring>
#include <queue>
#include <climits>
using namespace std;

struct ed{
	int u,next,w;
}e[300000];
struct path{
	int pre,ed;
}p[300000];
int n,m,s,t,x,y,w,ans,st=1,c[100000],fir[100000];
int d[100000]; queue<int> q; bool v[100000];

void add(int u,int v,int w){
	e[++st].u=v; e[st].next=fir[u]; e[fir[u]=st].w=w;
}

bool bfs()
{
	for (int i=1;i<=n;i++) v[i]=0,d[i]=INT_MAX/2,c[i]=fir[i];
	q.push(s); v[s]=1; d[s]=0;
	while (!q.empty())
	{
		int k=q.front(); q.pop();
		for (int i=fir[k];i;i=e[i].next)
		{
			int u=e[i].u,w=e[i].w;
			if (d[u]>d[k]+1&&w)
			{
				d[u]=d[k]+1;
				if (!v[u]) v[u]=1,q.push(u);
			}
		}
	}
	return (d[t]<INT_MAX/2);
}

int dfs(int p,int now)
{
	if (p==t) return now;
	int mw=0,used=0;
	for (int i=c[p];i;i=e[i].next)
	{
		c[p]=i;
		int u=e[i].u,w=e[i].w;
		if (w&&d[u]==d[p]+1) 
		//这里也要判断流量，不然死循 
		{
			if (mw=dfs(u,min(w,now-used)))
			{
				e[i].w-=mw; e[i^1].w+=mw; used+=mw;
				if (used==now) break;
			}
		}
	}
	return used;
}

int dinic()
{
	while (bfs())
	{
		ans+=dfs(s,INT_MAX/2);
	}
	return ans;
}

int main()
{
	cin>>n>>m>>s>>t;
	for (int i=1;i<=m;i++) {
		cin>>x>>y>>w; add(x,y,w); add(y,x,0);
	}
	cout<<dinic()<<endl;
}

$3.~ $最大流最小割

直接摘抄笔记了。

费用流问题

简单题意： 询问最大流的同时给每条边加一个边权，表示当前边的单位流量费用，询问最小花费。

对于最大流简单修改：

$~1.~$对于建边：

每次多加一个费用F，表示这条边的边权。对于反向边的话边权为-F，类比人流可以当做退款。

当然也可以类似求最大费用问题。只要通过将正边权变负，负边权变正再跑最小费用，取个绝对值就行啦！

$~2.~$对于EK算法：

只需跑关于费用F的最短路即可。

1. 因为如果你没有增广路了，你肯定就到不了终点，这里仍可用$d[t]<INF$判断；如果你有增广路，你肯定要优先选一条总费用最小的，于是跑最短路，使$\sum_s^t c[i]$最小即可。

2. 而且有细节要注意的是，这里的所有操作均和SPFA相同，尤其是入队出队之类的，EK本来是有向图而且是找单向流所以不要再标记$v[k]=0$，但SPFA要；顺便这里的权值是F，不是W，不要再打错了$QwQ$！

$~3.~ $对于Dinic算法：

由于EK费用流本质上还是找一条增广路处理一条增广路，效率照样低。我们当然还是想用Dinic多路增广的方式来提高效率，但具体应该怎么操作呢？

于是上古神犇zkw在发明主席树后又搞出了SPFA+dinic的费用流，太强辣%%%！

大体上就是把分层图的d[u]=d[k]+1改成加d[u]=d[k]+f（这部分和EK一样的）；同样在以Dinic的方式dfs里找增广路，而且仍可多路增广及弧优化！

对于dfs中的细节，由于这次分层方式是费用，所以会出现f=0的情况，所以只能通过访问标记的方法来规避死循了。。

具体来说就是将原来的DFS：

ll dfs(ll p,ll now)
{
	if (p==t) return now;
	ll used=0,mw=0;
	for (int i=c[p];i;i=e[i].next)
	{
		c[p]=i;
		ll u=e[i].u,w=e[i].w;
		if (w&&d[u]==d[p]+1)
		if (mw=dfs(u,min(now-used,w)))
		{
			e[i].w-=mw; e[i^1].w+=mw;
			used+=mw; if (used==now) break;	
		}
	}
	return used;
}

改成现在这样（已注释）：

int dfs(int p,int now)
{
	if (p==t) {
		v[t]=1; ans+=now; return now;  //找到终点就顺手记下流量了。。
	}
	int mw=0,used=0; v[p]=1;  //标记此点已访问
	for (int i=c[p];i;i=e[i].next)
	{
		c[p]=i; 
		int u=e[i].u,w=e[i].f; 
		if ((!v[u]||u==t)&&e[i].w&&d[u]==d[p]+w)
		//因为终点被标记了依然可以流过去
		{
			mw=dfs(u,min(e[i].w,now-used));
			if (mw) {
				cost+=w*mw; e[i].w-=mw; e[i^1].w+=mw; 
				used+=mw; if (now==used) break;
			}
		}
	}
	return used;
}

上下界费用流

咕咕，等做了那种题顺便再学吧。。

---

然后板子啥的就没了。。去做题吧！