链接1275Cashier Employment
题目大意就是说有一些人来应聘一个超级市场的工作，每个人的应聘的起始时间在0~23时之间，而超市在时间i需要R[i]个工作人员，而每个人的工作时间都是8小时，问最少需要多少人使得超市一天24小时满足超市的工作人数的需要。
设工作时间为1~24时，S[i]表示前i个小时所需要的工作人数的最小值，那么结果就可以表示成0为起点，24为终点的最短路。下面是约束不等式：
0<=S[i] - S[i-1]<= t[i] (1<=i<=24)
S[i] - S[i-8] >= R[i] (8<=i<=24)
S[i] + S[24] - S[i+16] >= R[i] (0<=i<=7)
整理之后：
S[i] - S[i-1] >= 0 (1<=i<=24)
S[i-1] - S[i] >= -t[i] (1<=i<=24)
S[i] - S[i-8] >= R[i] (8<=i<=24)
S[i] - S[i+16] >= R[i] - S[24] (0<=i<=7)
这样按照A-B >= W就可以建一些由B指向A的权值为W的有向边，求最长路。
或则是A指向B的权值为-W的有向边，并求其最短路。
另外，由于上图中S[24]是不知道的，所以枚举它就行，我是二分枚举的。
数据比较水（只有24个小时），用Bellman-Ford即可：
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define eps 1e-15
#define MAXN 25
#define INF 1000000007
#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a < b ? a : b)
#define mem(a) memset(a,0,sizeof(a)) struct EDGE
{
int v;
int w;
int next;
}edge[*MAXN];
int head[MAXN], d[MAXN],tot,T,N,R[MAXN],t[MAXN],ans,x; bool Bellman_Ford(int s)
{
for(int i=;i<=;i++) d[i] == (i==s)?:INF;
for(int k=;k<=;k++)
{
for(int i=;i<=;i++)
{
for(int e = head[i];d[i]!=INF && e!=-;e=edge[e].next)
{
if(d[edge[e].v]>d[i]+edge[e].w)
{
d[edge[e].v] = d[i] + edge[e].w;
}
}
}
}
for(int i=;i<=;i++)
{
for(int e = head[i];d[i]!=INF && e!=-;e=edge[e].next)
{
if(d[edge[e].v]>d[i]+edge[e].w)return false;
}
}
return true;
} void AddEdge(int u,int v,int w)
{
edge[tot].v = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot++;
} void BuildGragh(int NumOfPer)//由于每次总人数都不一样，所以需要重新建图
{
tot = ; mem(edge); memset(head,-,sizeof(head));
for(int i=;i<=;i++){AddEdge(i-,i,t[i]); AddEdge(i,i-,);}
for(int i=;i<=;i++) AddEdge(i,i-,-R[i]);
for(int i=;i<=;i++) AddEdge(i,i+,NumOfPer-R[i]);
AddEdge(,,-NumOfPer);
} void BSearch(int low,int high)//对总人数二分
{
if(low > high)return ;
int mid = (low + high) / ;
BuildGragh(mid);
if(Bellman_Ford())//表示可以找到一种解决方案
{
ans = mid;
BSearch(low, mid-);
}
else
{
BSearch(mid+,high);
}
} int main()
{
while(~scanf("%d", &T))while(T--)
{ mem(R); mem(t);
for(int i=;i<=;i++)
{
scanf("%d", &R[i]);
}
scanf("%d", &N);
for(int i=;i<N;i++){ scanf("%d", &x); t[x+]++;}
ans = -;
BSearch(,N);
if(ans == -) printf("No Solution\n");
else printf("%d\n",ans);
}
return ;
}