lp2604 ZJOI2010 网络扩容

第一问没什么好说的。直接看第二问。
一个很直接的想法就是,在每条边上都加上一条容量为\(k\),费用为\(c_{e}\)的边。
但是仔细一想会发现一个问题:如果s到t有多条路径的话,上述的方法就会使得流量总额过大。
有什么好方法呢?
第一个直接的想法是发现源汇之间如果有多条路径的话,那么必然是将所有的流量k全都贪心地放在花费最小的那条路径上是最优的。
但是这显然是不可能的,考虑一个残余网络非空的情况。
故而我们换一种思路:在原来所有边上额外连流量为k的边的同时,再从n向一个虚拟汇点t连一条边。这样既可完成。

#include<iostream>
#include<cstdio>
#include<queue>

const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}
struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[20005];
int h[20005],et=-1;
inline void Eadd(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int C){
	Eadd(U,V,W,C);
	Eadd(V,U,0,-C);
}
int n,m,s,t,K,dis[20005],nw[20005],val[20005],fa[20005],vis[20005];
int u[20005],v[20005],w[20005],c[20005];
std::queue<int> q;
inline bool SPFA(){
	for(int i=1;i<=t;++i){
		dis[i]=INF;
		val[i]=INF;
		vis[i]=0;
	}
	q.push(s);
	dis[s]=0,vis[s]=1,fa[t]=-1;
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dis[e[i].v]>dis[p]+e[i].c&&e[i].w>0){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(e[i].w,val[p]);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
	}
	return fa[t]!=-1;;
}

int answ=0,ansc=0;
inline void EK(){
	int p;
	while(SPFA()){
		p=t;
		answ+=val[t];
		ansc+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	} 
}


void init(){
	scanf("%d%d%d",&n,&m,&K);
	s=1,t=n;
	for(int i=1;i<=n+1;++i){
		h[i]=-1;
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d%d%d",u+i,v+i,w+i,c+i);
		add(u[i],v[i],w[i],0);
	}
	EK();
	printf("%d ",answ);
	for(int i=1;i<=m;++i){
		add(u[i],v[i],INF,c[i]);
	}
	add(t,t+1,K,0);
	++t;
	EK();
	printf("%d\n",ansc);
}

int main(){
	init();
	return 0;
}

lp2766 网络流24题-最长不下降子序列问题

这是一道看起来很简单的麻题。
很显然可以发现第一问就是直接n^2DP求一个答案。
第二问模拟寻找最长不下降子序列的过程。
第三问改几条边再跑一遍。
但是要注意很多很多细节。
比如说,建模的时候应该反着建。
再比如说,对于最长长度只有1的情况应当格外注意,因为这可能会导致各种错误。
写起来还是有点烦心的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>

const int INF=0x3f3f3f3f;
const int BIG=19260817;
inline int Min(int A,int B){
	return A<B?A:B;
}

inline int Max(int A,int B){
	return A>B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[250005];
int h[2005],et=-1;

inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et; 
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
}

int dep[2005],nw[2005],a[505];
int n,s,t,len;
std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF,nw[i]=h[i];
	}
	dep[s]=1;
	while(!q.empty()){
		q.pop();
	}
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
//	for(int i=1;i<=t;++i){
//		printf("%d ",dep[i]);
//	}
//	puts("");
	return dep[t]^INF;
}

inline int dfs(int X,int V){
	if(!V||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(V,e[i].w));
			if(val){
				cnt+=val;
				V-=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(!V){
					break;
				}
			}
		}
	}
	return cnt;
}
int f[505];
inline void slv1(){
	for(int i=1;i<=n;++i){
		f[i]=1;
		for(int j=1;j<i;++j){
			if(a[i]>=a[j]){
				f[i]=Max(f[i],f[j]+1);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		ans=Max(ans,f[i]);
	}
	len=ans;
	printf("%d\n",ans);
}

inline int dinic(){
	int RT=0;
	while(bfs()){
		RT+=dfs(s,INF);
	}
	return RT;
}

inline void slv2(){
	s=2*n+1,t=2*n+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	et=-1;
	for(int i=1;i<=n;++i){
		if(f[i]==len){
			add(i+n,t,1);
		}
		if(f[i]==1){
			add(s,i,1);
		}
		add(i,i+n,1);
		for(int j=1;j<i;++j){
			if(a[i]>=a[j]&&f[j]+1==f[i]){
				add(j+n,i,1);
			}
		}
	}
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
	}
	printf("%d\n",ans);
	add(1,n+1,BIG),add(s,1,BIG);
	if(f[n]==len){
		add(n,2*n,BIG),add(2*n,t,BIG);
	}
	while(bfs()){
		ans+=dfs(s,INF);
	}
	printf("%d\n",ans);
}

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	slv1();
	slv2();
}
int main(){
	init();
	return 0;
}

lp2764 网络流24题-最小路径覆盖问题


(其实建图方法已经写在题目里了。)
(这一题是一道匈牙利的裸题,考场上二分图最大匹配仍然建议使用匈牙利(因为在实现复杂度上有巨大优势),我纯粹练一下当前弧优化Dinic。)
首先有一个定理。将一张有向图上的每一个点都拆点成入点和出点,连边后形成一张二分图,那么原图的最小路径覆盖,就是顶点数减去这张二分图的最大匹配。
考虑感性地证明这个定理。
每一次匹配,事实上就意味着,一条路径可以额外走过一个点。这样就减少了一个路径覆盖。
所以,当匹配次数最大的时候,路径覆盖数就最小了。
答案用并查集处理一下输出。


#include<iostream>
#include<cstdio>
#include<queue>
const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[20005];
int h[2005],et=-1;
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
}
int dep[2005],nw[2005],f[2005];
int n,m,s,t;

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
}
inline int dfs(int X,int V){
	if(V<=0||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i; 
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(e[i].w,V));
			if(val){
				cnt+=val;
				V-=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(V<=0){
					break;
				}
			}
		}
	}
	return cnt;
}

inline int fnd(int X){
	for(int i=h[X+n];i>=0;i=e[i].nxt){
		if(1<=e[i].v&&e[i].v<=n){
			if(e[i].w){
				return e[i].v;
			}
		}
	}
	return X;
}
inline int fa(int X){
	return f[X]^X?f[X]=fa(f[X]):X;
}
inline void prnt(int X){
	for(int i=h[X];i>=0;i=e[i].nxt){
		if((n+1)<=e[i].v&&e[i].v<=(n<<1)&&!e[i].w){
			printf("%d ",e[i].v-n
			);
			prnt(e[i].v-n);
			return;
		}
	}
}
bool vis[2005];
void init(){
	scanf("%d%d",&n,&m);
	s=(n<<1)+1,t=(n<<1)+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int u,v;
	for(int i=1;i<=n;++i){
		add(s,i,1);
		add(n+i,t,1);
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(u,n+v,1);
	}
	int ans=n;
	while(bfs()){
		ans-=dfs(s,INF);
	}
	for(int i=1;i<=n;++i){
		f[i]=i;
	}
	for(int i=1;i<=n;++i){
		f[i]=fnd(i);
	}
	for(int i=1;i<=n;++i){
		fa(i);
	}
	for(int i=1;i<=n;++i){
		if(f[i]==i){
			printf("%d ",i);
			prnt(i);
			puts("");
		}
	}
	printf("%d\n",ans); 
}

int main(){
	init();
	return 0;
}

lp2763 网络流24题-试题库问题

对于这一题,我们建三层的边来描述题目中的约束。
对于每道题建一个点,源点连一条容量为1的边到每一个点,表示每道题最多只能被选取一次。
对于每个种类建一个点,每一个点连一条容量为1的边到它所属的所有类,表示它仅可以被作为这个类来选取。
每个种类连一条容量为这个种类需要的选取次数的边到汇点,表示这个种类最多需要被选取的次数。
然后,跑一遍当前弧优化Dinic最大流,如果需要选取的总题数都能选取到,流量就等于需要选取的总题数。
当然也可以大力拆点跑二分图匹配,不过那样似乎更难写的样子。

#include<iostream>
#include<cstdio>
#include<queue>
const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[40005];
int h[2005],et=-1;
int dep[2005],nw[2005];

inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}

inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0); 
}

int n,m,s,t,Sans=0,tot; 

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
} 
//V表示从源点到当前路径上的剩余流量,cnt表示这个点向后流了多少流量。 
inline int dfs(int X,int V){
	if(V<=0||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(V,e[i].w));
			if(val){
				cnt+=val;
				e[i].w-=val;
				e[i^1].w+=val;
				V-=val;
				if(V<=0){
					break;
				}
			}
		}
	}
	return cnt;
}

void init(){
	scanf("%d%d",&m,&n);
	s=m+n+1,t=m+n+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
//	注意初始化。 
	int p,x;
	for(int i=1;i<=m;++i){
		scanf("%d",&x);
		Sans+=x;
		add(n+i,t,x);
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&p);
		add(s,i,1);
		for(int j=1;j<=p;++j){
			scanf("%d",&x);
			add(i,n+x,1);
//			注意哈希。 
		}
	}
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
		printf("%d\n",ans); 
	}
	if(ans<Sans){
		puts("No solution!");
		return;
	}
	for(int i=1;i<=m;++i){
		printf("%d: ",i);
		for(int j=h[n+i];j;j=e[j].nxt){
			if((j&1)&&(e[j].w==1)&&(e[j].v!=t)){
				printf("%d ",e[j].v);
			}
		}
		puts("");
	}
}

int main(){
	init();
	return 0;
}

lp5030 长脖子鹿放置

观察这一题的攻击方式,我们可以发现一个特点——所有奇数行的长颈鹿都攻击不到偶数行的长颈鹿,反之亦然。
所以,我们对奇偶的长颈鹿分开考虑,这显然是一张二分图。
于是类同于骑士共存问题,我们建一个二分图,跑匈牙利。
对于\(200\)的数据范围,匈牙利的小常数是可以卡过去的。
但是T了两个点,获得了80分的好成绩。
然后我们考虑一个对于vis数组的常数优化。
对于vis数组,我们定义一个变量dep,表示当前是第dep次匹配。这样就不必每次都清空vis数组了。
第二个就是,由于连的边是确定的,故而我们可以在线计算目的边,这样可以减少很多寻址时间。
另外就是对图的遍历顺序的优化。用了出题人的松松松顺序之后最终通过此题。

#include<iostream>
#include<cstdio>

const int dx[8]={3,3,-3,-3,1,1,-1,-1};
const int dy[8]={-1,1,-1,1,3,-3,3,-3};

bool mp[205][205];
int vis[40405],dep=0;
int n,m,q,usd[40405];
//注意数组大小。 

inline int calc(int X,int Y){
	return (X<=0||Y<=0||X>n||Y>m||mp[X][Y])?0:X*m+Y;
} 

inline bool dfs(int X){
	int v;
	for(int i=0;i<8;++i){
		v=calc((X-1)/m+dx[i],(X-1)%m+1+dy[i]);
//		注意还原信息。 
		if(v&&vis[v]!=dep){
			vis[v]=dep;
			if(!usd[v]||dfs(usd[v])){
				usd[v]=X;
				return 1;
			}
		}
	}
	return 0;
}

void init(){
//	mp[n][m]->mp[x][y] 
	scanf("%d%d%d",&n,&m,&q);
	int x,y;
	for(int i=1;i<=q;++i){
		scanf("%d%d",&x,&y);
		mp[x][y]=1;
	}
	int ans=n*m-q;
	for(int i=1;i<=n;i+=2){
		for(int j=1;j<=m;++j){
			if(mp[i][j]){
				continue;
			}
			++dep;
			ans-=dfs(calc(i,j));
		}
	}
//	for(int i=0;i<=n+1;++i){
//		for(int j=0;j<=m+1;++j){
//			printf("%2d ",calc(i,j));
//		}
//		puts("");
//	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}

lp3355 网络流24题-骑士共存问题

首先我们观察这道题。
暴力地状压DP或者之类的操作显然会MLE/TLE。
我们发现,横坐标和纵坐标相加的和的奇偶性相同的格子永远不可能互相攻击到。
故而我们考虑建一张二分图。将横纵坐标的和的奇偶性不同的格子分别放在左右边,然后在能相互攻击到的点之间连边。依据题意,不能相互攻击到,所以答案即是这张图的最大独立集。

二分图最大独立集应当如何求得?我们有一个定理:一张二分图的最大独立集的大小等同于顶点数它的最大匹配的数量。
我们考虑感性地证明这个定理。
很容易可以发现,两个点不能被同时选取,当且仅当它们之间有连边。
又因为,有连边的两个点必然是属于二分图的两端的。
故而,如果有两个点不能被同时选取,它们必然可以构成一个匹配。
对于二分图上的最大匹配,所有没有被匹配的点都可以被选取。这非常的显然,因为没有被匹配到的点之间必然没有连边。如果有连边,那么就可以增加匹配,与最大匹配矛盾。
而,对于每一个匹配,都可以选取一组匹配中的一个点。这是因为,对于一些连通的匹配,它们有且仅有一个部分(左边或者右边)会和未匹配点连接。
这也是很显然的,因为如果不是这样的话,就存在一条新的增广路径,就可以得到更多的匹配了。
注意:坐标如何哈希成一个数字。

#include<iostream>
#include<cstdio>

const int dx[8]={-2,-1,1,2,-2,-1,1,2};
const int dy[8]={1,2,2,1,-1,-2,-2,-1}; 

struct ee{
	int v;
	int nxt;
}e[160005];
int h[40005],et=0;

inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et; 
}

bool vis[40005],mp[205][205];
int n=0,m=0,usd[40005];

inline int calc(int X,int Y){
	return (X-1)*n+Y;
//	注意坐标哈希成数字的方式。 
}

inline bool dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		if(!vis[e[i].v]){
			vis[e[i].v]=1;
			if(!usd[e[i].v]||dfs(usd[e[i].v])){
				usd[e[i].v]=X;
				return 1;
			}
		}
	}
	return 0;
}
int st[40005],tp=0;
char out[205][205];
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			mp[i][j]=0;
			usd[calc(i,j)]=0;
			out[i][j]='O';
		}
	}
	int x,y;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&x,&y);
		mp[x][y]=1;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
//			printf("[%d %d] ",i,j);
			if(mp[i][j]||((i+j)&1)){
//				注意不是每次跳2而是判奇偶性。 
				continue;
			}
			st[++tp]=calc(i,j);
			out[i][j]='@'; 
			//注意有障碍的不仅是结束点,还有出发点。 
			for(int k=0;k<8;++k){
				x=i+dx[k],y=j+dy[k];
				if(x<=0||y<=0||x>n||y>n||mp[x][y]){
					continue;
				}
				out[x][y]='X';
				add(calc(i,j),calc(x,y));
			}
		}
	}
//	for(int i=1;i<=n;++i){
//		for(int j=1;j<=n;++j){
//			putchar(out[i][j]);
//		}
//		puts("");
//	}
	int ans=n*n-m;
//	减去被挖掉的点 
	for(int i=1;i<=tp;++i){
		for(int j=1;j<=n*n;++j){
			vis[j]=0;
		}
		ans-=dfs(st[i]);
	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
} 

lp2756 网络流24题-飞行员配对方案问题

这是一个裸的配对问题。
我们可以建成一个二分图然后跑匈牙利。

#include<iostream>
#include<cstdio>
bool mp[105][105],vis[105];
int n,m,usd[105];

inline int dfs(int X){
    for(int i=1;i<=m;++i){
        if(!mp[X][i]){
            continue;
        }
        if(!vis[i]){
            vis[i]=1;
            if(!usd[i]||dfs(usd[i])){
                usd[i]=X;
                return 1;
            }
        }
    }
    return 0;
}

void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            mp[i][j]=mp[j][i]=0;
        }
    }
    int x=1,y=1;
    //你绝对想不到的错误——x,y没有初始化,导致判断它们的初始值的时候出现错误。 
    while(x>=0&&y>=0){
        scanf("%d%d",&x,&y);
        y-=n;
        mp[x][y]=1;
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            vis[j]=0;
        }
//        for(int j=1;j<=m;++j){
//        	printf("%d ",usd[j]);
//		}
//		puts("");
        ans+=(int)dfs(i);
    }
    printf("%d\n",ans);
    for(int i=1;i<=m;++i){
        if(usd[i]){
            printf("%d %d\n",usd[i],i+n);
            //注意这里要将编号还原。并且别输出反了。 
        }
    } 
}

int main(){
    init();
    return 0;
}

lp3376 【模板】网络最大流

全机房就我一个还不会网络流了。
下面我整理一下网络流的基本概念,辅助自己理解。


首先关于网络流的定义。形式化地说,网络流是一张图\(G(V,E)\)(有时也指这张图的一个状态),满足以下性质:
1.流量上限:对于任意一条边\(e\in E\),存在一个属性\(c_{e}\),定义它为这条边的流量上限。
2.流量受限:对于任意一条边\(e\in E\),存在一个属性\(0\le f_{e}\le c_{e}\),定义它为这条边当前的流量。
3.流量守恒:对于任意一个点\(v\),满足:\(\sum_{i\in{a|a_{v}=v,a\in E}}f_{i}=\sum_{j\in{b|b_{u}=v,b\in E}}f_{j}\)
4.源点汇点:存在两个点,分别叫做源点和汇点。其中,源点能够流出无穷多流量,而汇点能够流入无穷多流量。
若一个网络流的某一个状态满足上述所有性质,我们就称这个状态是合法的。
我们定义,对于一张网络流,使得它从源点流向汇点的流量最大的状态,为最大流。
求解最大流,就是指,求解最大流的状态。
为了辅助求解这个问题,我们可以考虑对于每一条边\(e\)都建一条反边\(e’\)。它的方向与原边相反。且\(f_{e’}=f_{e}\)
那么,所有的反边构成了另一张图\(G(E’,V)\),它描述的是它的原边已经走过的流量。
将一张图上的每一条边都只保留它的当前剩余流量\(f_{e}\),这张图可以被认为是对原图的流量空余的描述。故而我们称这张图为残余网络。

我们定义增广路径,指的是,在包括反边的残余网络的一条路径上面的一条路径,使得路径上的每一条原边都是不满的,且路径上每一条反边都是非空的。
对于关于这条路径上的所有原边,将其流量上限减去当前流量的值减去最小值,再对路径上每一条反边的当前流量值取最小值,再对两个最小值取最小值。
然后将所有原边的流量加上这个最小值,并将每一条反边的流量减去这个最小值(对应的反/原边同时减/加相应值)。 我们称这样一个操作为增广,称操作中减少反边流量的子操作为撤销。
如果当前图不是处于最大流的状态,那么一定可以找到一个增广路;如果当前图属于最大流的状态,那么一定没有增广路。
我们朴素地考虑如何利用增广来取得最大路径。如果我们每一次都暴力地寻找整个网络上的一条可行增广路并且增广(这似乎被称作F-F算法),在很糟糕的情况下,可能会出现很多次反复地增广而只增加很少的流量的情况。
在上诉的算法中,可能存在一种情况,就是,一条边被反复地增广-撤销多次。这样无形中增大了很多复杂度。
我们考虑上诉的情况是如何产生的。很显然,经过一次撤销操作之后,当前的路径的长度减少了一条边,而原来经过那条边的那些流量所在的路径上的长度也减少了一条边。
那么反复地增广-撤销操作的一个很大的原因,便是,第一次增广到这条边的时候的路径经过的边数太多。
如果每一次搜索增广路径的时候,都尽可能搜索边数尽可能少的一条边,那么便可以使得增广-撤销操作尽可能少。(这似乎被称作E-K算法)
上述的算法都可以被称作是朴素的算法。但复杂度最坏情况下可能会被卡到非常大,大概是\(O(n\times m^2)\)级。


下面是一个对于这个算法的正确性的感性证明。
我们首先证明,每一次增广之后,图上流过的流量都增多。
对于一次增广,当我们流过一条边的时候,流过的流量存在两种情况:
1.这些流量走过的是反边。
2.这些流量走过的是原边。
对于流过原边的流量,很显然无论如何可以流的,并且会将原图的状况改进得更优。
而对于流过反边的流量,可以视为将这些流量还原,然后原来流到这条边的那些流量,现在从当前路径流过这条边之后的那部分流走;而当前流到这条边的流量,则从之前流过这条边的那些流量的后半部分流走。
所以,每一次增广,总是会导向一个合法状态。
又因为,每一次增广之后,源点都会流出更多的流量,汇点都会收到更多的流量,所以整张图流过的流量增加了。

然后我们考虑证明,当不再能增广的时候,图上处于最大流的状态。
当走过一条边的时候,我们事实上完成了一次「反悔」,也就是指,让之前从这里走的一些流量往另一个方向走了。
如果,不再可以增广,这就意味着,无论反悔到什么程度、无论怎么改变之前已有的流量的路径,都无法找到一条新的路径使得流量可以通过。
即,哪怕是在反悔最多的情况下,也找不到一条能够产生更多流量的路径。
那么,我们就可以断言这个状态已经是最大流的状态了。


回到算法本身上。下面我们考虑优化这个朴素算法。\(O(n\times m^2)\)的复杂度显然是不可接受的。
Dinic算法就是一种对上述朴素算法的优化。
我们考虑一种被称为「多路增广」的操作。这种操作也是Dinic的核心。
对于每一次多路增广,我们首先将整张图dfs一遍,预处理出深度小于源汇距离的所有节点的深度。这样我们得到了一张分层图。
然后我们从源点开始进行一种特殊的DFS——每一次访问的节点的深度必须比前一个节点深,并且搜索经过的边必须是可以增广的边。
当我们搜索到汇点的时候,便开始沿着来路回溯,直到回溯到第一个「来路仍然可以继续增广」并且「连着其他还可以被继续增广的边」的节点为止,然后继续向下搜索。
如果回溯到了源点,多路增广结束。
然后,对剩下可以走的部分,重新计算深度,并重跑增广,直到不能再增广为止。
对于每一次多路增广,我们可以以\(O(nm)\)的复杂度遍历完成对某一个特定深度的所有增广操作。 而多路增广显然是最多只会被执行\(n\)次的。故而这么做的复杂度是\(O(n^2+m)\)的。
我们就得到了一个相对较优的算法。


#include<iostream>
#include<cstdio>
#include<queue>

const int INF = 0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[200005];
int h[10005],et=-1;
int n,m,s,t,ans=0,dep[10005],nw[10005];
inline void add(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=n;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
}

inline int dfs(int X,int V){
	if((V<=0)||(X==t)){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(V,e[i].w));
			if(val){
				cnt+=val;
				V-=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(V<=0){
					break;
				}
			}
		}
	}
	return cnt; 
}

void init(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	int u,v,w;
	for(int i=1;i<=n;++i){
		h[i]=-1;
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,0);
	}
	while(bfs()){
		ans+=dfs(s,INF);
		//注意应当填写起始点。 
	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0; 
}