【费用流】NOI2008志愿者招募

1061: [Noi2008]志愿者招募

Time Limit: 20 Sec Memory Limit: 162 MB
Submit: 5171 Solved: 3089
[Submit][Status][Discuss]

Description

　　申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难

题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要

Ai 个人。布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用

是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这

并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。

Input

　　第一行包含两个整数N, M，表示完成项目的天数和可以招募的志愿者的种类。接下来的一行中包含N 个非负

整数，表示每天至少需要的志愿者人数。接下来的M 行中每行包含三个整数Si, Ti, Ci，含义如上文所述。为了

方便起见，我们可以认为每类志愿者的数量都是无限多的。

Output

　　仅包含一个整数，表示你所设计的最优方案的总费用。

Sample Input

3 3
2 3 4
1 2 2
2 3 5
3 3 2

Sample Output

HINT

1 ≤ N ≤ 1000，1 ≤ M ≤ 10000，题目中其他所涉及的数据均不超过2^31-1。

Source

试题分析：这题并不需要线性规划。。。

　　　　　最小可行费用流是可做的，而且简单的多：

　　　　　　　　　我们先考虑每天的限制，每天开一个点，点限制[Ai,INF]。

　　　　　　　　　然后将每一天之间连单向边(向下一天)，费用0，边限制[0,INF]

　　　　　　　　　最后对于每个三元组(s,t,c)只需将t向s连一条费用为c，边限制[0,INF]的边。

　　　　　关于怎么限制点，只需要拆点(1个变为2个)然后将入边连都接到一个点上，将出边连接到另外一个点上，在这两个点之间建一条与点限制相同点边。　　　　

　　　　　然后求一遍无源汇最小可行性费用流即可。

代码：

#include<iostream>

#include<cstring>

#include<vector>

#include<queue>

#include<cstdio>

#include<algorithm>

using namespace std;

#define LL long long

inline int read(){

	int x=0,f=1;char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0';

	return x*f;

}

const int INF=9999999;

const int MAXN=300000*3;

int N,M;

int S,T;

int Root[MAXN+1],Node[MAXN+1],Next[MAXN+1],Cost[MAXN+1],C[MAXN+1];

int dis[MAXN+1]; bool inq[MAXN+1];

int cnt;

void insert(int u,int v,int w,int c){

	Node[cnt]=v; Cost[cnt]=c;

	C[cnt]=w; Next[cnt]=Root[u];

	Root[u]=cnt; ++cnt; return ;

}

bool BFS(){

	memset(inq,false,sizeof(inq));

	for(int i=0;i<=N;i++) dis[i]=INF;

	dis[T]=0; inq[T]=true;

	deque<int> Que; Que.push_front(T);

	while(!Que.empty()){

		int k=Que.front(); Que.pop_front();

		for(int x=Root[k];x>-1;x=Next[x]){

			int v=Node[x];

			if(C[x^1]>0&&dis[v]>dis[k]-Cost[x]){

				dis[v]=dis[k]-Cost[x];

				if(!inq[v]){

					inq[v]=true;

					if(!Que.empty()&&dis[Que.front()]>=dis[v]) Que.push_front(v);

					else Que.push_back(v);

				}

			}

		}

		inq[k]=false;

	}

	return dis[S]<INF;

}

int ans=0;

int DFS(int k,int t){

	if(k==T){inq[T]=1;return t;}

	int res=0; inq[k]=1;

	for(int x=Root[k];x>-1;x=Next[x]){

		int v=Node[x];

		if(C[x]>0&&!inq[v]&&dis[v]==dis[k]-Cost[x]){

			int tmp=DFS(v,min(C[x],t));

			if(!tmp) continue;

			t-=tmp; ans+=tmp*Cost[x]; C[x]-=tmp; C[x^1]+=tmp;

			res+=tmp;

			if(!t) return res;

		}

	}

	return res;

}

int main(){

    N=read(),M=read();

    for(int i=0;i<MAXN;i++) Root[i]=-1;

	S=2*N+1,T=2*N+2;

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

		int t=read();

		insert(i,i+N,INF,0);

		insert(i+N,i,0,0);

		insert(S,i+N,t,0);

		insert(i+N,S,0,0);

		insert(i,T,t,0);

		insert(T,i,0,0);

	}

	for(int i=1;i<N;i++)

		insert(i+N,i+1,INF,0),insert(i+1,i+N,0,0);

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

		int u=read(),v=read(),c=read();

		insert(v+N,u,INF,c);

		insert(u,v+N,0,-c);

	}

	N=N*2+2;

	--cnt;

	while(BFS()) {

		DFS(S,INF);

	}

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

	return 0;

}

秒客网