BZOJ1061 [NOI2008]志愿者招募

starli posted @ 2016年1月24日 11:31 in 网络流 , 101 阅读

听说这道题可以用线性规划的方法水过去,但是这是一道网络流题

以下引用自百度

设每个时间i都需要有至少Ai个志愿者,设每种志愿者i使用了xi个,那么我们对于每个时间点都可以列出一个不等式:x1+x2+x3+...+xn>=Ai(其中如果第i类志愿者不能在该区间工作则xi固定为0)。

最后要求最小化w1*x1+w2*x2+x3*x3+...+wn*xn(其中wi是第i种志愿者的单位价格)。

这正是一个线性规划的问题。

那么我们是否可以转化为网络流来求解呢?

当然是可以哒~

现在我们将每个点的Ai取反,变成-Ai,这样他就成了一个“坑”了(相对于y=0而言),我们从源点S给最左边的时间点引流,流的大小为U(U为大整数),然后每个时间点i向时间点i+1建边(i,i+1,U-Ai,0),最后设汇点为最右端的时间点。

现在,如果所有时间点的Ai都为0,那么显然,汇点的流量恰好等于U。

问题来了,现在我们有的Ai不等于0了,那么显然源点到汇点的流量被这些“坑”所截断了,怎么解决这一个问题?

假设志愿者工作的时间为【Li,Ri】,且该种志愿者单位花费为Ci,则我们建边(Li,Ri+1,INF,Ci),表示我们雇佣了一些志愿者“填坑”来了,如果雇佣了xi个志愿者,则说明将该区间内的所有“坑”的深度填掉了xi(当然可能有的坑在“填坑”行动后高于y=0,那也无所谓了嘛,多多益善~)。

那么现在是不是看起来思路有一点清晰了?

于是志愿者的作用就是一个人可以填一个区间的“坑”(好厉害!),然后需要每种志愿者选择一些使得花费最小的情况下填掉所有的“坑”,就是这样~

最后就是让费用流帮我们选择志愿者的时候了~

于是我们按照上面的方法跑完一遍最小费用最大流,如果流量等于U,则说明满流(志愿者们成功填掉了所有的坑,同志们辛苦了~),此时的记录的cost就是最小值(cost为算法记录的最小费用)。如果流量不等于U则无解。

这时我们又收获了一种费用流的模型:初始给一道大流,然后将有至少覆盖次数限制的点(边)的权值取反变成“坑”,最后区间覆盖就等于“填坑”,只要最后的流量等于大流的流量,就有解。

或者看这个题解 http://blog.csdn.net/fzhvampire/article/details/50889187

接下来是代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100010,INF=1000000000;
int to[N*2],from[N*2],pre[N*2],cost[N*2],flow[N],q[N],l,r,inq[N],dis[N],now[N],prev[N],tail=1,n,m,a,s,t,c,left=INF,ans;
void add(int u,int v,int cap,int co){to[++tail]=v;from[tail]=u;pre[tail]=now[u];now[u]=tail;cost[tail]=co;flow[tail]=cap;}
bool spfa(int s,int t){
	for(int i=1;i<=n+2;i++) dis[i]=INF;
	l=r=0;q[++r]=s;inq[s]=1;dis[s]=0;
	while(l<r){
		int x=q[(++l)%N];inq[x]=0;
		for(int i=now[x];i;i=pre[i]) if(flow[i]>0){
			if(dis[to[i]] > dis[x] + cost[i]) {
				dis[to[i]]=dis[x]+cost[i],prev[to[i]]=i;
				if(!inq[to[i]]) q[(++r)%N]=to[i],inq[to[i]]=1;
			}
		}
	}
	return dis[t]!=INF;
}
int zg(int s,int t){
	int f=INF,sum=0;
	for(int i=t;i!=s;i=from[prev[i]]) f=min(f,flow[prev[i]]);
	for(int i=t;i!=s;i=from[prev[i]]) flow[prev[i]]-=f,flow[prev[i]^1]+=f,sum+=cost[prev[i]]*f;
	return sum;
}
int main(){
	//freopen("1061.in","r",stdin);freopen("1061.out","w",stdout);
	scanf("%d%d",&n,&m);
	add(n+2,1,INF,0);add(1,n+2,0,0);
	for(int i=1;i<=n;i++) scanf("%d",&a),add(i,i+1,INF-a,0),add(i+1,i,0,0);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&s,&t,&c),add(s,t+1,INF*2,c),add(t+1,s,0,-c);
	while(spfa(n+2,n+1)) 
	ans+=zg(n+2,n+1);
	printf("%d",ans);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter