网络流 学习笔记 ①

刚刚A了网络最大流，其实仔细思考网络流的过程还是挺简单的，只是因为它的修正思路比较独特，会让人有点难懂，但是最大流本身还是好理解的。
先上EK的代码：

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1e4+5,maxm=1e5+5;

inline int read(){
	char ch=getchar();
	int r=0,s=1;
	while(ch>57||ch<48)s=ch==45?0:s,ch=getchar();
	while(ch>=48&&ch<=57)r=r*10+ch-48,ch=getchar();
	return s?r:-r;
}

queue < int > q;
struct edge{int fa,to,nxt,f,c,rs;}e[maxm<<1];
int n,m,st,ed,cnt,ans;
int head[maxn],a[maxn],pre[maxn];

void add(int u,int v,int w){
	e[++cnt]=(edge){u,v,head[u],0,w,cnt+1},head[u]=cnt;
	e[++cnt]=(edge){v,u,head[v],0,0,cnt-1},head[v]=cnt;
	return;
}

bool Get_maxf(){
	int u,v;
	memset(a,0,sizeof(a));
	while(q.size())q.pop();
	q.push(st),pre[st]=0,a[st]=inf;
	while(q.size()){
		u=q.front(),q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			v=e[i].to;
			if(!a[v]&&e[i].c>e[i].f){
				a[v]=min(a[u],e[i].c-e[i].f);
				pre[v]=i;
				q.push(v);
			}
		}
		if(a[ed])break;
	}
	if(!a[ed])return 0;
	for(int i=ed;i!=st;i=e[pre[i]].fa){
		e[pre[i]].f+=a[ed];
		e[e[pre[i]].rs].f-=a[ed];
	}
	ans+=a[ed];
	return 1;
}
		  
int main(){
	n=read(),m=read(),st=read(),ed=read();
	for(int i=1,x,y,z;i<=m;++i)x=read(),y=read(),z=read(),add(x,y,z);
	while(Get_maxf());
	printf("%d
",ans);
	return 0;
}

然后我去咕下Dinic

$Update : $ Dinic咕完了，现在先扔这里，要是联赛没退役就更

code :

#include<bits/stdc++.h>
#define MIN(A,B) (A>B?B:A)
#define inf 0x7fffffff
using namespace std;
const int maxm=1e5+5,maxn=1e4+5;

inline int read(){
	char ch=getchar();
	int r=0,s=1;
	while(ch>57||ch<48)s=ch==45?0:s,ch=getchar();
	while(ch>=48&&ch<=57)r=r*10+ch-48,ch=getchar();
	return s?r:-r;
}

queue < int > q;
struct edge{int to,nxt,c,rs;}e[maxm<<1];
int n,m,S,T,cnt,ans;
int head[maxn],dep[maxn];

void add(int u,int v,int w){
	e[++cnt]=(edge){v,head[u],w,cnt+1},head[u]=cnt;
	e[++cnt]=(edge){u,head[v],0,cnt-1},head[v]=cnt;
	return;
}

bool bfs(){
	int x,y;
	memset(dep,0,sizeof(dep));
	dep[S]=1;
	while(q.size())q.pop();
	q.push(S);
	while(q.size()){
		x=q.front(),q.pop();
		for(int i=head[x];i;i=e[i].nxt){
			y=e[i].to;
			if(e[i].c&&!dep[y]){
				dep[y]=dep[x]+1;
				q.push(y);
			}
		}
	}
	return dep[T]?1:0;
}

int dfs(int u,int t,int f){
	if(u==t||f==0)return f;
	int res=0;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(e[i].c&&dep[v]==dep[u]+1){
			int tmp=dfs(v,t,MIN(e[i].c,f));
			res+=tmp,f-=tmp;
			e[i].c-=tmp;
			e[e[i].rs].c+=tmp;
		}
	}
	return res;
}

int main(){
	n=read(),m=read(),S=read(),T=read();
	for(int i=1,x,y,z;i<=m;++i)x=read(),y=read(),z=read(),add(x,y,z);
	while(bfs())ans+=dfs(S,T,inf);
	printf("%d
",ans);
	return 0;
}

咕咕咕