网络流入门

碎碎念

开学了qaq

24号真的忙活了一整天，才把寝室收拾好

晚上十一点半上的床，结果认床睡不着

大概十二点半睡着的，结果第二天早上五点半就醒了

我直接起床好吧，六点二十卡点出门

嘿嘿，开开心心上大学

--------碎碎念到此结束，下面是正文（手动分割线）--------

FF(Ford-Fulkerson)

网络流的本质为找增广路，即从源点到汇点的路

增广路边权最小值即为答案，建反边即为反悔机制

FF的本质是用DFS去完成这个过程，由于不具有一些最优性

复杂度会与流的大小有关，不是很优

EK(Edmond-Karp)

EK则是用BFS来优化，BFS能保证其每次搜到的一定是最短的增广路

复杂度则与边有关，较优，却不够

Dinic

Dinic的思想是先用BFS对图进行分层，再做DFS的FF算法

先用BFS求出每个点的层数，在DFS时每次只往层数高的方向走

同时启用多路增广，每次找到一条路后若有剩余流量，继续从当前节点DFS下去

并且运用当前弧优化，因为在Dinic算法中启用了多路增高

大致思路就是会榨干每一条边的价值，所以一条边只需要遍历一次

保证了最优性的情况下优化了时间，是一种较为常用的网络流算法

（这是口嗨，Dinic还没学会呢）

WA了好几发，我终于调对了洛谷模板！

第一次忘记加判断层高MLE

第二次没开long long见祖宗WA

第三次向下传递状态的时候直接传递了原来的流而非剩余流WA

/*
BFS分层
DFS只往层数高的地方走
多路增广，每次用尽流
当前弧优化，一条边只走一次 
*/
#include<bits/stdc++.h>
#define int long long
#define inf 1e10
using namespace std;
int n,m,s,t,ans;
int cnt=-1,head[210],edge[10010],to[10010],nxt[10010];
int dep[210],cur[210];
queue<int>q;
int bfs()
{
	memset(dep,-1,sizeof(dep));
	memcpy(cur,head,sizeof(head));
	dep[s]=0,q.push(s);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=head[u];i!=-1;i=nxt[i])
		{
			int v=to[i],w=edge[i];
			if(dep[v]!=-1||edge[i]==0)continue;
			dep[v]=dep[u]+1,q.push(v);
		}
	}
	return dep[t]!=-1;
} 
int dfs(int u,int f)
{
	if(u==t)return f;
	int ret=f;
	for(int i=cur[u];i!=-1&&ret;i=nxt[i])
	{
		cur[u]=i;
		int v=to[i],w=edge[i];
		if(w==0||dep[v]<=dep[u])continue;
		int r=dfs(v,min(ret,w));
		if(r==-1)continue;
		ret-=r,edge[i]-=r,edge[i^1]+=r;
	}
	return f-ret;
}
signed main()
{
	memset(head,-1,sizeof(head));
	memset(nxt,-1,sizeof(nxt));
	scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
		cnt++,edge[cnt]=w,to[cnt]=v,nxt[cnt]=head[u],head[u]=cnt;
		cnt++,edge[cnt]=0,to[cnt]=u,nxt[cnt]=head[v],head[v]=cnt;
	}
	while(bfs())ans+=dfs(s,inf);
	printf("%lld\n",ans);
	return 0;
}