POJ 1275 Cashier Employment(差分约束)

时间:2023-03-08 19:49:13
POJ 1275 Cashier Employment(差分约束)

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

题意 : 一家24小时营业的超市,要雇出纳员,需要求出超市每天不同时段需要的出纳员数,午夜只需一小批,下午需要多些,希望雇最少的人,给出每小时需要的出纳员的最少数量,R(0),R(1),...,R(23)。R(0)表示从午夜到凌晨1:00所需要出纳员的最少数目;R(1)表示凌晨1:00到2:00之间需要的;以此类推。这些数据每一天都是相同的。有N人申请这工作,申请者 i ,从一个特定的时刻开始连续工作恰好8小时。定义ti(0<=ti<=23)为上面提到的开始时刻,也就是说,如果第i个申请者被录用,他)将从 ti 时刻开始连续工作8小时。

思路 :差分约束,挺难的,看了好多人的题解,才稍微懂一些了,http://972169909-qq-com.iteye.com/blog/1185527,这个神写的不错,,,还有黑书上也有解释

POJ 1275 Cashier Employment(差分约束)

其实说的有点那啥,我一开始也还是没怎么看懂

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue> using namespace std; const int INF = ;
struct node
{
int u,v,w ;
int next ;
} map[] ;
bool flag[] ;
int cnt,pre[],cntt[],dist[] ;
int r[],t[] ; void addedge(int u,int v,int w)
{
map[cnt].v = v ;
map[cnt].w = w ;
map[cnt].next = pre[u] ;
pre[u] = cnt++ ;
} void Init()
{
cnt = ;
memset(pre,-,sizeof(pre)) ;
memset(cntt,,sizeof(cntt)) ;
memset(flag,false,sizeof(flag)) ;
} bool spfa(int start)
{
queue<int >Q ;
for(int i = ; i < ; i++)
dist[i] = -INF ;
dist[start] = ;
Q.push(start) ;
flag[start] = true ;
while(!Q.empty())
{
int u = Q.front() ;
Q.pop() ;
if(++cntt[u] > )
return false ;
flag[u] = false ;
for(int i = pre[u] ; i + ; i = map[i].next)
{
int v = map[i].v ,w = map[i].w;
if(dist[v] < dist[u] + w)
{
dist[v] = dist[u] + w ;
if(!flag[v])
{
flag[v] = true ;
Q.push(v) ;
}
}
}
}
return true ;
}
int main()
{
int T ;
scanf("%d",&T) ;
while(T--)
{
for(int i = ; i <= ; i++)
scanf("%d",&r[i]) ;
int N ,s;
scanf("%d",&N) ;
memset(t,,sizeof(t)) ;
for(int i = ; i < N ; i++)
{
scanf("%d",&s) ;
t[s + ]++ ;
}
int low = ,high = N ;
bool flagg = false ;
while(low < high)
{
Init() ;
int mid = (low+high)>> ;
for(int i = ; i <= ; i++)
{
addedge(i-,i,) ;
addedge(i,i-,-t[i]) ;
}
for(int i = ; i <= ; i++)
addedge(i-,i,r[i]) ;
for(int i = ; i <= ; i++)
addedge(i+,i,r[i]-mid) ;
addedge(,,mid) ;
if(spfa())
{
high = mid ;
flagg = true ;
}
else low = mid+ ;
}
if(flagg)
printf("%d\n",high) ;
else printf("No Solution\n") ;
}
return ;
}