基础网络流做题方法简单归纳与整理

bool bfs()
{
	for(int i=1;i<=n;i++)dis[i]=inf;//注意初始化是否完全，这里的 n 可以写为 t
	while(q.size())q.pop();
	q.push(s),dis[s]=0,now[s]=head[s];
	int u;
	while(q.size())
	{
		u=q.front(),q.pop();
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].to;
			if(e[i].val&&dis[v]==inf)
			{
				dis[v]=dis[u]+1,now[v]=head[v],q.push(v);
				if(v==t)return 1;
			}
		}
	}
	return 0;
}
int dfs(int u,int flow)
{
	if(u==t)return flow;
	int t,res=0;
	for(int i=now[u];i&&flow;i=e[i].nxt)
	{
		int v=e[i].to;
		now[u]=i;//当前弧优化
		if(e[i].val&&dis[v]==dis[u]+1)
		{
			t=dfs(v,min(e[i].val,flow));
			if(!t)dis[v]=inf;
			e[i].val-=t,e[i^1].val+=t,res+=t,flow-=t;
		}
	}
	return res;
}//真的 dinic

bool spfa()
{
	for(int i=1;i<=n;i++)dis[i]=inf,vis[i]=0;
	memcpy(now,head,sizeof head);
	while(q.size())q.pop();
	q.push(s),dis[s]=0,vis[s]=1;
	int u;
	while(q.size())
	{
		u=q.front(),q.pop(),vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].to;
			if(e[i].val&&dis[v]>dis[u]+e[i].cost)
			{
				dis[v]=dis[u]+e[i].cost;
				if(!vis[v])q.push(v),vis[v]=1;
			}
		}
	}
	return dis[t]!=inf;
}//spfa 建分层图
int dfs(int u,int flow)
{
	if(u==t)return flow;
	vis[u]=1;
	int x,res=0;
	for(int &i=now[u];i&&res<flow;i=e[i].nxt)
	{
		int v=e[i].to;
		if(!vis[v]&&e[i].val&&dis[v]==dis[u]+e[i].cost)
		{
			x=dfs(v,min(e[i].val,flow-res));
			if(x)e[i].val-=x,e[i^1].val+=x,res+=x,cst+=x*e[i].cost;
		}
	}
	vis[u]=0;
	return res;
}//这里用的是正规的 dinic，模板题题解几乎全是 EK