POJ 1275 Cashier Employment 挺难的差分约束题

http://poj.org/problem?id=1275

题目大意：

一商店二十四小时营业，但每个时间段需求的雇员数不同（已知，设为R[i]），现有n个人申请这份工作，其可以从固定时间t连续工作八个小时，问在满足需求的情况下最小需要多少个雇员。

思路：

挺难的。。看了别人的思路搞半天。。

设num[ i ]为i时刻能够开始工作的人数，x[ i ]为实际雇佣的人数，那么x[ I ]<=num[ I ]。设r[ i ]为i时刻至少需要工作的人数，于是有如下关系：

x[ I-7 ]+x[ I-6 ]+…+x[ I ]>=r[ I ]

设s[ I ]=x[ 1 ]+x[ 2 ]…+x[ I ]，

得到

s[ I ]-s[ I-1 ]>=0 (0<=I<=23)

s[ I-1 ]-s[ I ]>=-num[ I ] (0<=I<=23)

s[ I ]-s[ I-8 ]>=r[ I ] (8<=I<=23)

s[ I ]-s[ I+16 ]>=r[ I ]-s[ 23 ] (0<=I<= 7)

这里出现了小的困难，我们发现以上式子并不是标准的差分约束系统，因为在最后一个式子中出现了三个未知单位。但是注意到其中跟随 I变化的只有两个，于是s[23]就变得特殊起来，看来是需要我们单独处理，于是我们把 s[ 23 ]当作已知量放在右边。

经过这样的整理，整个图就很容易创建了，将所有形如 A-B>=C 的式子我们从节点B 引出一条有向边指向 A 边的权值为C （这里注意由于左右确定，式子又是统一的>=的不等式，所以A和B是相对确定的，边是一定是指向A的），图就建成了。最后枚举所有s[ 23 ]的可能值，对于每一个s[23]，我们都进行一次常规差分约束系统问题的求解，判断这种情况是否可行，如果可行求出需要的最优值，记录到Ans中，最后的Ans的值即为所求。

不过按上面的死活出不来。最后和别人一样下标都+1过了。。。。。不知道嘛状况。

还有要加上0->24的边（看POJ discuss的）

大牛解释如下：

为避免负数，时间计数1～24。令：

R[i] i时间需要的人数（1<=i<=24）

T[i] i时间应聘的人数（1<=i<=24）

x[i] i时间录用的人数（0<=i<=24），其中令x[0]=0

再设s[i]=x[0]+x[1]+……+x[i] （0<=i<=24），

由题意，可得如下方程组：

(1) s[i]-s[i-8]>=R[i] (8<=i<=24)

(2) s[i]-s[16+i]>=R[i]-s[24] (1<=i<=7)

(3) s[i]-s[i-1]>=0 (1<=i<=24)

(4) s[i-1]-s[i]>=-T[i] (1<=i<=24)

这个差分约束有个特殊的地方，(2)的右边有未知数s[24]。

这时可以通过枚举s[24]=ans来判断是否有可行解。

即(2)变形为(2') s[i]-s[16+i]>=R[i]-ans (1<=i<=7)

再通过SPFA求解(1)(2')(3)(4)。

不过最后有可能出现这种情况：

(1)(2')(3)(4)虽然有解，但求出的s[24]小于代入(2')里的ans！

这时，显然得到的s[]不满足原来的(2)了（请仔细比较(2)与(2')）。

不过虽然得到的解不满足原方程组，但这并不代表(1)(2)(3)(4)在s[24]=ans时没有可行解！

此外，值得注意的是，当得到的s[24]>ans时，虽然s[24]不一定是最优解，但把ans置成s[24]后，确实是可行解。

所以，简单把(2)置换成(2')是有问题的！

为了等价原命题，必须再加上条件：s[24]>=ans

这就是所谓加出来的那条边（5） s[24]－s[0]>=ans

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int MAXN=23+10;

const int MAXM=3000;

const int INF=-9999999;

struct edge

{

	int to;

	int val;

	int next;

}e[MAXM];

int head[MAXN],dis[MAXN],len,m;

int num[MAXN],r[MAXN];

void add(int from,int to,int val)

{

	e[len].to=to;

	e[len].val=val;

	e[len].next=head[from];

	head[from]=len++;

}

bool spfa(int k)

{

	int start=0;

	for(int i=0;i<=24;i++)

		dis[i]=INF;

	bool vis[MAXN]={0};

	int cnt[MAXN]={0};

	queue<int> q;

	q.push(start);

	vis[start]=1;

	cnt[start]=1;

	dis[start]=0;

	while(!q.empty())

	{

		int cur=q.front();

		q.pop();

		vis[cur]=false;

		for(int i=head[cur];i!=-1;i=e[i].next)

		{

			int id=e[i].to;

			if(dis[id] < dis[cur] + e[i].val)

			{

				dis[id]=dis[cur] + e[i].val;

				if(!vis[id])

				{

					if(++cnt[id] > 24)

						return false;

					vis[id]=true;

					q.push(id);

				}

			}

		}

	}

	if(k!= dis[24])

		return false;

	return true;

}

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		memset(num,0,sizeof(num));

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

			scanf("%d",&r[i]);

		scanf("%d",&m);

		for(int i=0;i<m;i++)

		{

			int t;

			scanf("%d",&t);

			num[t+1]++;

		}

		bool ok=false;

		for(int k=0;k<=m;k++)

		{

			memset(head,-1,sizeof(head));

			len=0;

			add(0,24,k);

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

			{

				add(i-1,i,0);

				add(i,i-1,-num[i]);

				if(i>8)

					add(i-8,i,r[i]);

				else

					add(i+16,i,r[i]-k);

			}

			if(spfa(k) )

			{

				ok=true;

				break;

			}

		}

		if(!ok)

			puts("No Solution");

		else

			printf("%d\n",dis[24]);

	}

	return 0;

}

巴特西

POJ 1275 Cashier Employment 挺难的差分约束题

最新文章

热门文章