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

• OI-WIKI上の最大流
• OI-WIKI上の费用流

1.最大流

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

EK最大流模板:

//this code can get 81 points in P3381,which is a template problem.  
#include 
#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 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 
#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 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

#include 
#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