NOI 2008 志愿者招募 employee

« NOI 2008 设计路线 design

NOI 2008 假面舞会 party »

三 06

NOI 2008 志愿者招募 employee

这道题正确的解法是构造网络，求网络最小费用最大流，但是模型隐藏得较深，不易想到。构造网络是该题的关键，以下面一个例子说明构图的方法和解释。

例如一共需要4天，四天需要的人数依次是4,2,5,3。有5类志愿者，如下表所示：

种类	1	2	3	4	5
时间	1-2	1-1	2-3	3-3	3-4
费用	3	4	3	5	6

设雇佣第i类志愿者的人数为X[i]，每个志愿者的费用为V[i]，第j天雇佣的人数为P[j]，则每天的雇佣人数应满足一个不等式，如上表所述，可以列出

P[1] = X[1] + X[2] >= 4

P[2] = X[1] + X[3] >= 2

P[3] = X[3] + X[4] +X[5] >= 5

P[4] = X[5] >= 3

对于第i个不等式，添加辅助变量Y[i] (Y[i]>=0) ，可以使其变为等式

P[1] = X[1] + X[2] – Y[1] = 4

P[2] = X[1] + X[3] – Y[2] = 2

P[3] = X[3] + X[4] +X[5] – Y[3] = 5

P[4] = X[5] – Y[4] = 3

在上述四个等式上下添加P[0]=0,P[5]=0，每次用下边的式子减去上边的式子，得出

① P[1] – P[0] = X[1] + X[2] – Y[1] = 4

② P[2] – P[1] = X[3] – X[2] -Y[2] +Y[1] = -2

③ P[3] – P[2] = X[4] + X[5] – X[1] – Y[3] + Y[2] =3

④ P[4] – P[3] = – X[3] – X[4] + Y[3] – Y[4] = -2

⑤ P[5] – P[4] = – X[5] + Y[4] = -3

观察发现，每个变量都在两个式子中出现了，而且一次为正，一次为负。所有等式右边和为0。接下来，根据上面五个等式构图。

每个等式为图中一个顶点，添加源点S和汇点T。

如果一个等式右边为非负整数c，从源点S向该等式对应的顶点连接一条容量为c，权值为0的有向边；如果一个等式右边为负整数c，从该等式对应的顶点向汇点T连接一条容量为c，权值为0的有向边。

如果一个变量X[i]在第j个等式中出现为X[i]，在第k个等式中出现为-X[i]，从顶点j向顶点k连接一条容量为∞，权值为V[i]的有向边。

如果一个变量Y[i]在第j个等式中出现为Y[i]，在第k个等式中出现为-Y[i]，从顶点j向顶点k连接一条容量为∞，权值为0的有向边。

构图以后，求从源点S到汇点T的最小费用最大流，费用值就是结果。

根据上面的例子可以构造出如下网络，红色的边为每个变量X代表的边，蓝色的边为每个变量Y代表的边，边的容量和权值标已经标出(蓝色没有标记，因为都是容量∞，权值0)。

在这个图中求最小费用最大流，流量网络如下图，每个红色边的流量就是对应的变量X的值。

所以，答案为4*3+2*3+3*6=36。

上面的方法很神奇得求出了结果，思考为什么这样构图。我们将最后的五个等式进一步变形，得出以下结果

① – X[1] – X[2] + Y[1] + 4 = 0

② – X[3] + X[2] + Y[2] – Y[1] – 2 = 0

③ – X[4] – X[5] + X[1] + Y[3] – Y[2] + 3 = 0

④ X[3] + X[4] – Y[3] + Y[4] – 2 = 0

⑤ X[5] – Y[4] – 3 = 0

可以发现，每个等式左边都是几个变量和一个常数相加减，右边都为0，恰好就像网络流中除了源点和汇点的顶点都满足流量平衡。每个正的变量相当于流入该顶点的流量，负的变量相当于流出该顶点的流量，而正常数可以看作来自附加源点的流量，负的常数是流向附加汇点的流量。因此可以据此构造网络，求出从附加源到附加汇的网络最大流，即可满足所有等式。而我们还要求最小，所以要在X变量相对应的边上加上权值，然后求最小费用最大流。

我写的是朴素的SPFA算法求增广路的最小费用流算法，可以在题目时限内通过所有测试点。

在NOI的现场上，该题得分的平均分12.56，只有高逸涵大牛拿到了满分。不能不说这是一道难题，难就难在抽象出问题的数学模型，设计有效的算法。而信息学竞赛正朝着这个方向发展，数学建模将是解决问题的共同关键步骤。

^?View Code CPP

/* 
 * Problem: NOI2008 employee
 * Author: Guo Jiabao
 * Time: 2009.3.2 14:03
 * State: Solved
 * Memo: SPFA最小费用最大流
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=1003,MAXM=10002*4,INF=0x7FFFFFFF;
using namespace std;
struct edge
{
	edge *next,*op;
	int t,c,v;
}ES[MAXM],*V[MAXN];
struct Queue
{
	int Q[MAXN],QH,QL,Size;
	bool inq[MAXN];
	inline void ins(int v)
	{
		if (++QL>=MAXN)
			QL=0;
		Q[QL]=v;
		inq[v]=true;
		Size++;
	}
	inline int pop()
	{
		int r=Q[QH];
		inq[r]=false;
		Size--;
		if (++QH>=MAXN)
			QH=0;
		return r;
	}
	inline void reset()
	{
		memset(Q,0,sizeof(Q));
		QH=Size=0;
		QL=-1;
	}
}Q;
int N,M,S,T,EC=-1;
int demond[MAXN],sp[MAXN],prev[MAXN];
edge *path[MAXN];
inline void addedge(int a,int b,int v,int c=INF)
{
	edge e1={V[a],0,b,c,v} , e2={V[b],0,a,0,-v};
	ES[++EC]=e1; V[a]=&ES[EC];
	ES[++EC]=e2; V[b]=&ES[EC];
	V[a]->op=V[b]; V[b]->op=V[a];
}
void init()
{
	int i,a,b,c;
	freopen("employee.in","r",stdin);
	freopen("employee.out","w",stdout);
	scanf("%d%d",&N,&M);
	for (i=1;i<=N;i++)
		scanf("%d",&demond[i]);
	for (i=1;i<=M;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		addedge(a,b+1,c);
	}
	S=0,T=N+2;
	for (i=1;i<=N+1;i++)
	{
		c = demond[i] - demond[i-1];
		if (c>=0)
			addedge(S,i,0,c);
		else
			addedge(i,T,0,-c);
		if (i>1)
			addedge(i,i-1,0);
	}
}
bool spfa()
{
	int u,v;
	for (u=S;u<=T;u++)
		sp[u]=INF;
	Q.reset();
	Q.ins(S);
	sp[S]=0;
	prev[S]=-1;
	while (Q.Size)
	{
		u=Q.pop();
		for (edge *k=V[u];k;k=k->next)
		{
			v=k->t;
			if (k->c>0 && sp[u] + k->v <sp[v])
			{
				sp[v]=sp[u] + k->v;
				prev[v]=u;
				path[v]=k;
				if (!Q.inq[v])
					Q.ins(v);
			}
		}
	}
	return sp[T]!=INF;
}
int argument()
{
	int i,delta=INF,flow=0;
	edge *e;
	for (i=T;prev[i]!=-1;i=prev[i])
	{
		e=path[i];
		if (e->c<delta)
			delta=e->c;
	}
	for (i=T;prev[i]!=-1;i=prev[i])
	{
		e=path[i];
		e->c-=delta;e->op->c+=delta;
		flow+=e->v*delta;
	}
	return flow;
}
int maxcostflow()
{
	int Flow=0;
	while (spfa())
		Flow += argument();
	return Flow;
}
int main()
{
	init();
	printf("%dn",maxcostflow());
	return 0;
}

志愿者招募

【问题描述】

申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。

布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。

【输入格式】

输入文件的第一行包含两个整数N, M，表示完成项目的天数和可以招募的志愿者的种类。

接下来的一行中包含N 个非负整数，表示每天至少需要的志愿者人数。

接下来的M 行中每行包含三个整数Si, Ti, Ci，含义如上文所述。为了方便起见，我们可以认为每类志愿者的数量都是无限多的。

【输出格式】

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

【输入样例】
3 3
2 3 4
1 2 2
2 3 5
3 3 2
【输出样例】
14
【样例说明】

招募3 名第一类志愿者和4 名第三类志愿者。

【数据规模和约定】

30%的数据中，1 ≤ N, M ≤ 10，1 ≤ Ai ≤ 10；

100%的数据中，1 ≤ N ≤ 1000，1 ≤ M ≤ 10000，题目中其他所涉及的数据均

不超过2^31-1。

21 Responses to “NOI 2008 志愿者招募 employee”

QuantyZhao Says:
三月 6th, 2009 at 20:33:35
你也开始做NOI2008的题了么？速度真快啊

[回复]
CmYkRgB123 Says:
三月 6th, 2009 at 21:07:23
没有那么快，先做而已。

[回复]
CmYkRgB123 » Blog Archive » NOI 2008 解题报告 Says:
三月 19th, 2009 at 13:57:56
[...] NOI 2008 志愿者招募 employee [...]
xlmj531 Says:
四月 18th, 2009 at 09:30:27
能否讲解一下高逸涵的做法

[回复]
CmYkRgB123 Says:
四月 18th, 2009 at 13:02:48
求“高逸涵的做法”

我也不会

[回复]
Ethan Vector Says:
五月 2nd, 2009 at 18:34:23
赞……您这种以构建函数以及不等式来发现题目内部的规律的思想让我很受启发，数学建模的作用非常关键。

[回复]
zjybest Says:
九月 28th, 2009 at 17:50:05
有收获

[回复]
largelymfs Says:
二月 6th, 2010 at 22:25:59
为什么建模对了，用spfa扩展法只能得到90分（我是pascal）,求教

[回复]

BYVoid 回复:
二月 11th, 2010 at 11:05:44

是超時嗎？

[回复]

largelymfs 回复:
二月 21st, 2010 at 13:00:44

嗯，超了一点1.3s

[回复]
Edward_mj Says:
二月 11th, 2010 at 01:19:58
你确定通过了所有的测试数据？我也是有一个超时，而且把你的程序copy到cena最后一个点也是超时。可能是我的电脑太慢了吧。时限是2S，而我的程序最后一个点跑了6.53s，你的跑了4.90s。

[回复]

BYVoid 回复:
二月 11th, 2010 at 11:05:22

我當然通過了所有測試數據，而且是在我的2001年買的電腦上。你的電腦的確太慢了，不過不一定是硬件因素，請檢查運行環境。

[回复]
Edward_mj Says:
二月 11th, 2010 at 19:40:49
额，但是我还存在一个疑问，那对于你的这一步：

对于第i个不等式，添加辅助变量Y[i] (Y[i]>=0) ，可以使其变为等式

P[1] = X[1] + X[2] – Y[1] = 4

P[2] = X[1] + X[3] – Y[2] = 2

P[3] = X[3] + X[4] +X[5] – Y[3] = 5

P[4] = X[5] – Y[4] = 3

在上述四个等式上下添加P[0]=0,P[5]=0，每次用下边的式子减去上边的式子，得出

① P[1] – P[0] = X[1] + X[2] – Y[1] = 4

② P[2] – P[1] = X[3] – X[2] -Y[2] +Y[1] = -2

③ P[3] – P[2] = X[4] + X[5] – X[1] – Y[3] + Y[2] =3

④ P[4] – P[3] = – X[3] – X[4] + Y[3] – Y[4] = -2

⑤ P[5] – P[4] = – X[5] + Y[4] = -3

前面的等式加上P[0]=0,P[5]=0，一共六个式子。
设这六个式子为命题p。
后面五个式子为命题q。
那么有p=>q，即p是q的充分不必要条件。（q不能推出p）
然后你的流量守恒是根据后面的5个式子搞出来的。
所以我可以这么认为：
p=>q流量守恒
由于q和流量守恒等价，可以写成p=>流量守恒。
所以满足流量守恒不一定满足p，所以它们不是等价的。
对不对呢？

[回复]

Edward_mj 回复:
二月 11th, 2010 at 19:45:31

p=>q（等价符号）流量守恒 //居然显示不出来。。。

[回复]

BYVoid 回复:
二月 11th, 2010 at 21:53:12

我沒看懂你的意思，“后面五个式子为命题q”是什麽？

[回复]

Edward_mj 回复:
二月 12th, 2010 at 01:24:46

这个。。是我表述不规范了。
应该表述为“后面五个式子都成立”为命题q
“前6个式子都成立”为命题p
我的总的意思就是
p能推出q
而q不能推出p
而q与“流量守恒”等价
所以“流量守恒”不能推出p~
也就是说，流量守恒，不代表是可行解，因为只有前6个式子都成立才是可行解。

[回复]
Edward_mj Says:
二月 13th, 2010 at 20:51:45
噢，是我傻X了，流量守恒与可行解不等价，但最大流和可行解是等价的。。。

[回复]
lqp18_31 Says:
二月 14th, 2010 at 11:08:31
我用的是标号的费用流，全部数据加起来不到2s。问一下，spfa可以处理负环吗？（标号法不行）有什么方法可以处理负环费用流呢？

[回复]
darin Says:
三月 6th, 2010 at 23:23:12
“如果一个变量X[i]在第j个等式中出现为X[i]，在第k个等式中出现为-X[i]，从顶点j向顶点k连接一条容量为∞，权值为V[i]的有向边.”
“每个正的变量相当于流入该顶点的流量，负的变量相当于流出该顶点的流量，”
我沙茶..有点不理解呀…x[i]在第j个等式中正,,不是相当于从k这个点流出流入j这个点么,,那为什么不是k向j连边额.??

[回复]

yacht 回复:
六月 2nd, 2010 at 22:08:00

貌似神牛是把等式两边同时乘以了一个-1……

[回复]
yacht Says:
六月 2nd, 2010 at 22:11:05
请问那个经典的餐巾计划问题如果也用等式的方式来分析是怎样的呢？

[回复]

Beyond the Void

NOI 2008 志愿者招募 employee

志愿者招募

相關日誌

21 Responses to “NOI 2008 志愿者招募 employee”

Leave a Reply

订阅

閱讀習慣

页面

搜索

分类目录

最受欢迎

存档

Recent Comments

标签

关于