《网 络 瘤:从入门到入土》第一卷

\[\huge\color{cornflowerblue}{\texttt{Net flow studying notes: NO.1.}} \]

\[\large\color{gold}{\texttt{Only Templates Here.}} \]


\[\texttt{updated on 2021.10.31:} \]

\[\texttt{我透 刚才都没发现我SSP的当前弧优化加到狗身上去了(((} \]

\[\texttt{加了快150ms} \]



1.最大流

分为复杂度\(O(nm^2)\)的EK和\(O(n^2m)\)的Dinic.

EK最大流模板:

//this code can get 81 points in P3381,which is a template problem.  
#include <bits/stdc++.h>
#define int long long 
#define MAXN 2000001
#define INF 1e8+10
using namespace std;

inline int r()
{
	int fed=0;
	bool flag=1;
	char in=getchar();
	while(!isdigit(in))
	flag&=(in!='-'),in=getchar();
	while(isdigit(in))
	fed=fed*10+in-'0',in=getchar();
	return (2*flag-1)*fed;
}

int n,m,s,t;
int ans;
int head[MAXN],cntr;
int A[MAXN],path[MAXN];

struct edge{
	int u,v,next,flow;
}e[MAXN];

inline void add(int u,int v,int flow)
{
	e[cntr].u=u;
	e[cntr].v=v;
	e[cntr].flow=flow;
	e[cntr].next=head[u];
	head[u]=cntr++;
}

inline void orz(int u,int v,int flow)
{
	add(u,v,flow);
	add(v,u,0);
}

inline void EK()
{
	while(true)
	{
		memset(A,0,sizeof(A));
		queue<int> q;
		q.push(s);
		A[s]=INF;
		while(!q.empty())
		{
			int u=q.front();
			q.pop();
			for(int i=head[u];~i;i=e[i].next)
			{
				int v=e[i].v;
				if(!A[v]&&e[i].flow)
				{
					path[v]=i;
					A[v]=min(A[u],e[i].flow);
					q.push(v);
				}
			}
			if(A[t])
			break;
		}
		if(!A[t])
		break;
		for(int i=t;i!=s;i=e[path[i]].u)
		{
			e[path[i]].flow-=A[t];
			e[path[i]^1].flow+=A[t];
		}
		ans+=A[t];
	}
}

signed main()
{
	memset(head,-1,sizeof(head));
	n=r(),m=r();
	s=r(),t=r();
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		u=r(),v=r();
		w=r();
		orz(u,v,w);
	}
	EK();
	printf("%lld",ans);
	return 0;
} 

Dinic最大流模板:

//100 points in P3381.
#include <bits/stdc++.h>
#define ri register int
#define int long long
#define MAXN 1000001
using namespace std;
const int INF=0x7fffffff;

int n,m,s,t;
int depth[MAXN],head[MAXN],cur[MAXN],cntr;
//queue<int> q;

struct node{
	int to,next,flow;
}e[MAXN<<2];

inline void add(int u,int v,int flow)
{
	e[cntr].to=v;
	e[cntr].flow=flow;
	e[cntr].next=head[u];
	head[u]=cntr++;
}

inline void orz(int u,int v,int flow)
{
	add(u,v,flow);
	add(v,u,0);
}

inline int r()
{
	int fed=0;
	char i=getchar();
	bool flag=1;
	while(!isdigit(i))
	flag&=(i!='-'),i=getchar();
	while(isdigit(i))
	fed=fed*10+i-'0',i=getchar();
	return (2*flag-1)*fed;
}

int q[MAXN];

inline bool bfs()
{
	memset(depth,-1,sizeof(depth));
	depth[s]=1;
	cur[s]=head[s];
	int l=0,r=1;
	q[++l]=s;
	while(l<=r)
	{
		int u=q[l++];
		for(ri i=head[u];~i;i=e[i].next)
		{
			int v=e[i].to;
			if(depth[v]==-1&&e[i].flow)
			{
				depth[v]=depth[u]+1;
				q[++r]=v;
				cur[v]=head[v];
				if(v==t)
				return true;
			}
		}
	}
	return 0;
}

inline int dfs(int now,int fl)
{
	if(now==t||fl==0)
	return fl;
	int tflow=0;
	for(ri i=cur[now];~i&&tflow<fl;i=e[i].next)
	{
		cur[now]=i;
		int v=e[i].to;
		if(depth[v]==depth[now]+1&&e[i].flow)
		{
			int cf=dfs(v,min(e[i].flow,fl-tflow));
			if(!cf)
			depth[v]=-1;
			e[i].flow-=cf;
			e[i^1].flow+=cf;
			tflow+=cf;
		}
	}
	return tflow;
}

inline void Dinic()
{
	int res=0,ad=0;
	while(bfs())
	{
		while(ad=dfs(s,INF))
		res+=ad;
	}
	printf("%lld",res);
}

signed main()
{
	n=r(),m=r();
	s=r(),t=r();
	memset(head,-1,sizeof(head));
	for(ri i=1;i<=m;i++)
	{
		int u,v,w;
		u=r(),v=r();w=r();
		orz(u,v,w);
	}
	Dinic();
	return 0;
}

2.最小费用最大流

目前只会写SSP算法,用SPFA替代Dinic里的bfs来求最少花费的增广路.

SSP模板:

#include <bits/stdc++.h>
#define MAXN 50005
#define ri register int
using namespace std;
const int INF=0x3f3f3f3f;

inline int r()
{
	int fed=0;
	char in=getchar();
	bool flag=1;
	while(!isdigit(in))
	flag&=(in!='-'),in=getchar();
	while(isdigit(in))
	fed=fed*10+in-'0',in=getchar();
	return (2*flag-1)*fed;
}

int n,m,s,t,cntr,head[MAXN];
int ans,res;
int dist[MAXN];
bool vis[MAXN];
int q[MAXN<<2];
int cur[MAXN];

struct node{
	int to,next,flow,cost;
}e[MAXN<<2];

inline void add(int u,int v,int w,int c)
{
	e[cntr].to=v;
	e[cntr].flow=w;
	e[cntr].cost=c;
	e[cntr].next=head[u];
	head[u]=cntr++;
}

inline void orz(int u,int v,int w,int c)
{
	add(u,v,w,c);
	add(v,u,0,-c);
}

inline bool SPFA()
{
	//已死
	//算法
	//重现
	//光辉
	//(↑)
	memset(dist,0x3f,sizeof(dist));
	memcpy(cur,head,sizeof(head));
	int l=0,r=1;
	q[++l]=s,dist[s]=0;
	vis[s]=1;
	while(l<=r)
	{
		int u=q[l++];
		vis[u]=0;
		for(ri i=head[u];~i;i=e[i].next)
		{
			int v=e[i].to;
			if(e[i].flow&&dist[v]>dist[u]+e[i].cost)
			{
				dist[v]=dist[u]+e[i].cost;
				if(!vis[v])
				vis[v]=1,q[++r]=v;
			}
		}
	}
	return dist[t]!=INF;
}

inline int dfs(int now,int maxfl)
{
	if(now==t||maxfl==0)
	return maxfl;
	vis[now]=1;
	int cytti=0;
	for(ri i=cur[now];~i&&cytti<maxfl;i=e[i].next)
	{
		cur[now]=i;
		int v=e[i].to;
		if(!vis[v]&&e[i].flow&&dist[v]==dist[now]+e[i].cost)
		{
			int cf=dfs(v,min(e[i].flow,maxfl-cytti));
			if(cf)
			{
				ans+=cf*e[i].cost;
				e[i].flow-=cf;
				e[i^1].flow+=cf;
				cytti+=cf;
			}
		}
	}
	vis[now]=0;
	return cytti;
}

inline void Dinic()
{
	int ad=0;
	while(SPFA())
		while(ad=dfs(s,INF))
		res+=ad;
	printf("%d %d",res,ans);
}

int main()
{
	memset(head,-1,sizeof(head));
	n=r(),m=r();
	s=r(),t=r();
	for(ri i=1;i<=m;i++)
	{
		int u,v,w,c;
		u=r(),v=r();
		w=r(),c=r();
		orz(u,v,w,c);
	}
	Dinic();
	return 0;
}

\[\color{skyblue}{\texttt{And We,}} \]

\[\color{skyblue}{\texttt{We Burn Faster Than Lights,}} \]

\[\color{skyblue}{\texttt{Shine Across In The Night Sky,}} \]

\[\color{skyblue}{\texttt{We Burn Faster Than Lights.}} \]

\[\color{gold}{◢_◤} \]

上一篇:2021-05 04


下一篇:《网 络 瘤:从入门到入土》第一卷