题目

题目大意

给你一个有向图，每个点开始有一定的水量（可能为负数），可以通过边流到其它点。

每条边的流量是有上下界的。

每个点的水量可以增加或减少（从外界补充或泄出到外界），但是需要费用，和增加（减少）流量呈正比例函数关系。

每条边的流量也需要费用，费用和流量呈二次函数关系（常数项为\(0\)）。

问将所有水流完的最小花费。

思考历程

这显然是一道上下界最小费用可行流嘛！

有源有汇的上下界可行流的做法：建立超级源\(ss\)和超级汇\(tt\)（和\(S\)、\(T\)），对于\(u\)到\(v\)的容量为\([low,up]\)的边。这时从\(ss\)到\(v\)连一条容量为\(low\)的边，\(u\)到\(tt\)连一条容量为\(low\)的边，\(u\)到\(v\)连一条\(up-low\)的边。并且要从\(T\)到\(S\)连一条容量为无限大的边。

具体原因不再赘述。

对于每个点的初始水量，如果为正数，就从\(S\)向它连一条容量上下界都为水量的边，费用为\(0\)。

如果为负数，就从\(T\)向它连一条容量上下界都为水量的绝对值的边，费用为\(0\)。

对于每个点和外界之间的关系，可以从\(S\)到它连一条上限为无限大的边，它到\(T\)连一条上限为无限大的边，费用由题目给定。

可是最麻烦的来了，这个二次函数该怎么处理呢？

想不出来……

最终交了个错误的程序上去，成功爆0……

正解

前面的都差不多了，就只有二次函数的那一部分。

二次函数为\(y=ax^2+bx\)，直接搞似乎不行，那就试着将它们拆开，变成\(a+b\)、\(3a+b\)、\(5a+b\)……这些边。每条边的容量为\(1\)。

具体来说，当\(x\)变成\(x+1\)时，费用就会新增\(a(2x+1)+b\)

由于我们跑的是最小费用可行流，一定会先跑更小的边。所以这种方法是不可能WA的。

但是如果直接这样拆，边会很多啊！想一想，要拆成最多\(100\)条边……

于是就有了动态加边大法！

一开始只加入\(a+b\)的边，如果这条边被流满，那就加一条\(3a+b\)的边，以此类推……

当然，由于上下界的问题，一开始加的并不是\(a+b\)。先将最低费用\(a*low^2+b*low\)加入答案。为了使费用不重复计算，\(ss\)到\(v\)和\(u\)到\(tt\)的边就不需要费用了，只是中间那条\(u\)到\(v\)的边初始费用变成了\(a(2low+1)+b\)。

至此整道题就解决了。

代码

独爱zkw费用流……

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cassert>

#define min(a,b) ((a)<(b)?(a):(b))

#define INF 1000000000

#define N 1000

int n,m;

struct EDGE{

	int to,c,w;

	EDGE *las;

	int sp;

} e[100000];

int ne;

EDGE *last[N];

#define rev(ei) (e+(int((ei)-e)^1))

inline void link(int u,int v,int c,int w,int sp=0){

	e[ne]={v,c,w,last[u],sp};

	last[u]=e+ne++;

	e[ne]={u,0,-w,last[v],0};

	last[v]=e+ne++;

}

int nsp;

int mx[100000],ad[100000];

int ex[100000];

inline void link2(int u,int v,int low,int up,int a,int b){

	nsp++;

	mx[nsp]=up,ad[nsp]=a*2,ex[nsp]=low+1;

	e[ne]={v,1,a*(2*low+1)+b,last[u],nsp};

	last[u]=e+ne++;

	e[ne]={u,0,-(a*(2*low+1)+b),last[v],0};

	last[v]=e+ne++;

}

int s,t,ss,tt;

int mincost;

int dis[N];

int vis[N],BZ;

int dfs(int x,int s){

	if (x==tt){

		mincost+=dis[ss]*s;

		return s;

	}

	int have=s;

	vis[x]=BZ;

	for (EDGE *ei=last[x];ei;ei=ei->las)

		if (vis[ei->to]!=BZ && ei->c && dis[x]==dis[ei->to]+ei->w){

			int t=dfs(ei->to,min(have,ei->c));

			ei->c-=t,rev(ei)->c+=t,have-=t;

			if (ei->sp && ex[ei->sp]<mx[ei->sp]){

				link(x,ei->to,1,ei->w+ad[ei->sp],ei->sp);

				ex[ei->sp]++;

				ei->sp=0;

			}

			if (!have)

				return s;

		}

	return s-have;

}

inline bool change(){

	int d=INF;

	for (int i=1;i<=n+4;++i)

		if (vis[i]==BZ)

			for (EDGE *ei=last[i];ei;ei=ei->las)

				if (vis[ei->to]!=BZ && ei->c)

					d=min(d,dis[ei->to]+ei->w-dis[i]);

	if (d==INF)

		return 0;

	for (int i=1;i<=n+4;++i)

		if (vis[i]==BZ)

			dis[i]+=d;

	return 1;

}

inline void zkw(){

	do

		do

			BZ++;

		while (dfs(ss,INF));

	while (change());

}

int main(){

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

	s=n+1,t=n+2,ss=n+3,tt=n+4;

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

		int left,in,out;

		scanf("%d%d%d",&left,&in,&out);

		if (left>0)

			link(ss,i,left,0),link(s,tt,left,0);

		else if (left<0)

			link(ss,t,-left,0),link(i,tt,-left,0);

		link(s,i,INF,in);

		link(i,t,INF,out);

	}

	link(t,s,INF,0);

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

		int u,v,a,b,low,up;

		scanf("%d%d%d%d%d%d",&u,&v,&a,&b,&low,&up);

		mincost+=a*low*low+b*low;

		if (a){

			if (low)

				link(ss,v,low,0),link(u,tt,low,0);

			if (up-low)

				link2(u,v,low,up,a,b);

		}

		else{

			if (low)

				link(ss,v,low,b),link(u,tt,low,0);

			if (up-low)

				link(u,v,up-low,b);

		}

	}

	zkw();

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

	return 0;

}

总结

题目的难点主要在拆边，事实上，这似乎有点套路啊……

所以当直接做不方便时，可以试着作差，然后就出来一些东西……

巴特西

[JZOJ3302] 【集训队互测2013】供电网络

题目

题目大意

思考历程

正解

代码

总结

最新文章

热门文章