[Poj1273]Drainage Ditches（网络流）

Description

给图，求最大流

最大流模板题，这里用dinic

Code

#include <cstdio>

#include <cstring>

#include <algorithm>

#define Inf 0x7fffffff

#define N 210

using namespace std;

int g[N][N],d[N],q[N*10],h,t;

int n,m,Ans,tmp;

bool Bfs(){

	memset(d,-1,sizeof(d));

	d[1]=0;

	h=0,t=1;

	q[1]=1;

	while(h<t){

		int u=q[++h];

		for(int v=1;v<=n;++v)

			if(d[v]<0&&g[u][v]>0){

				d[v]=d[u]+1;

				q[++t]=v;

			}

	}

	return d[n]>0;

}

int dfs(int u,int low){

	if(u==n) return low;

	int tmp;

	for(int v=1;v<=n;++v){

		if(g[u][v]>0&&d[v]==d[u]+1&&(tmp=dfs(v,min(low,g[u][v])))){

			g[u][v]-=tmp;

			g[v][u]+=tmp;

			return tmp;

		}

	}

	return 0;

}

int main(){

	while(~scanf("%d%d",&m,&n)){

		memset(g,0,sizeof(g));

		for(int i=1,u,v,f;i<=m;++i){

			scanf("%d%d%d",&u,&v,&f);

			g[u][v]+=f;

		}

		Ans=0;

		while(Bfs()) {

			while(tmp=dfs(1,Inf)) Ans+=tmp;

		}

		printf("%d\n",Ans);

	}

	return 0;

}

下面是sap算法，

#include <cstdio>

#include <algorithm>

#include <cstring>

#define Inf 0x7fffffff

#define N 110

using namespace std;

struct info{

	int nex,fr,to,f;

}e[N*N];

int n,m,Ans,dis[N],head[N],cnt[N],S,T,tot;

void Link(int u,int v){

	e[++tot].nex=head[u];

	e[tot].f=1;e[tot].fr=u;e[tot].to=v;head[u]=tot;

	e[++tot].nex=head[v];

	e[tot].f=0;e[tot].fr=v;e[tot].to=u;head[v]=tot;

}

int sap(int u,int delta){

	int sum=0,mins=n;

	if(u==T) return delta;

	for(int i=head[u];i;i=e[i].nex){

		int v=e[i].to;

		if(e[i].f>0&&dis[u]==dis[v]+1){

			int save=sap(v,min(delta-sum,e[i].f));

			sum+=save;

			e[i].f-=save;

			e[i^1].f+=save;

			if(dis[S]>=n||sum==delta) return sum;

		}

		if(e[i].f>0) mins=min(mins,dis[v]);

	}

	if(sum==0){

		if(!(--cnt[dis[u]])) dis[S]=n;

		else ++cnt[dis[u]=mins+1];

	}

	return sum;

}

int main(){

	scanf("%d%d",&m,&n);

	S=0,T=n+1;tot=-1;//异或取反向边，所以从0开始编号

	int u,v,tmp;

	while(~scanf("%d%d",&u,&v)){

		if(u+v==-2) break;

		Link(u,v);

	}

	for (int i=1;i<=m;++i) Link(S,i);

    for (int i=m+1;i<=n;++i) Link(i,T);

    n+=2;cnt[0]=n;

	while(dis[S]<n) Ans+=sap(S,Inf);

	printf("%d\n",Ans);

	return 0;

}