BZOJ 1834 ZJOI2010 network 网络扩展 Dinic+EK费用流

标题效果：给定一个n积分m无向图边，每一方有一个扩展的成本c。代表扩张1费用的交通，寻求最大流量和扩大的最大流量k最小成本

第一问直接运行的最大流量

第二个问题将是连接到一个流的末端每个边缘的起点是正无穷大、费用c缘然后，n汇点被连接到流动ans+k 费用为0的边跑最小费用最大流就可以

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define M 5010

#define INF 0x3f3f3f3f

#define S 1

#define T (n+1)

using namespace std;

struct edge{

	int x,y,f,c;

}edges[M];

struct abcd{

	int to,f,c,next;

}table[M<<2];

int head[M],tot=1;

int n,m,k,ans,anscost;

int dpt[M];

void Add(int x,int y,int f,int c)

{

	table[++tot].to=y;

	table[tot].f=f;

	table[tot].c=c;

	table[tot].next=head[x];

	head[x]=tot;

}

bool BFS()

{

	static int q[M],r,h;

	int i;

	memset(dpt,-1,sizeof dpt);

	r=h=0;q[++r]=S;dpt[S]=1;

	while(r!=h)

	{

		int x=q[++h];

		for(i=head[x];i;i=table[i].next)

			if(table[i].f&&!~dpt[table[i].to])

			{

				dpt[table[i].to]=dpt[x]+1;

				q[++r]=table[i].to;

				if(table[i].to==T)

					return true;

			}

	}

	return false;

}

int Dinic(int x,int flow)

{

	int i,left=flow;

	if(x==T) return flow;

	for(i=head[x];i&&left;i=table[i].next)

		if(table[i].f&&dpt[table[i].to]==dpt[x]+1)

		{

			int temp=Dinic(table[i].to,min(left,table[i].f) );

			if(!temp) dpt[table[i].to]=-1;

			left-=temp;

			table[i].f-=temp;

			table[i^1].f+=temp;

		}

	return flow-left;

}

bool EK()

{

	static int q[65540],flow[M],cost[M],from[M];

	static bool v[M];

	static unsigned short r,h;

	int i;

	memset(cost,0x3f,sizeof cost);

	cost[S]=0;flow[S]=INF;q[++r]=S;

	while(r!=h)

	{

		int x=q[++h];v[x]=0;

		for(i=head[x];i;i=table[i].next)

			if(table[i].f)

				if(cost[table[i].to]>cost[x]+table[i].c)

				{

					cost[table[i].to]=cost[x]+table[i].c;

					flow[table[i].to]=min(flow[x],table[i].f);

					from[table[i].to]=i;

					if(!v[table[i].to])

						v[table[i].to]=1,q[++r]=table[i].to;

				}

	}

	if(cost[T]==INF) return false;

	anscost+=flow[T]*cost[T];

	for(i=from[T];i;i=from[table[i^1].to])

		table[i].f-=flow[T],table[i^1].f+=flow[T];

	return true;

}

int main()

{

	int i;

	cin>>n>>m>>k;

	for(i=1;i<=m;i++)

	{

		scanf("%d%d",&edges[i].x,&edges[i].y);

		scanf("%d%d",&edges[i].f,&edges[i].c);

		Add(edges[i].x,edges[i].y,edges[i].f,0);

		Add(edges[i].y,edges[i].x,0,0);

	}

	Add(n,T,INF,0);

	Add(T,n,0,0);

	while( BFS() )

		ans+=Dinic(S,INF);

	table[tot-1].f=k;

	for(i=1;i<=m;i++)

	{

		Add(edges[i].x,edges[i].y,INF,edges[i].c);

		Add(edges[i].y,edges[i].x,0,-edges[i].c);

	}

	while( EK() );

	cout<<ans<<' '<<anscost<<endl;

}

秒客网

BZOJ 1834 ZJOI2010 network 网络扩展 Dinic+EK费用流

相关文章