poj1275收银员——差分约束

做的第一道差分约束题...

首先，根据题意得出一些不等关系(f为前缀和雇佣人数)：

0 <= f[i] - f[i-1] <= t[i]; // 雇佣的人数少于申请者但不能为负数
f[i] - f[i-8] >= r[i] // 当x>=8时，该方程成立，否则将出现负数显然不成立
f[i-8+24] - f[i] <= x - r[i] // 当x<8时，由于昨天的雇人可以通宵上班，因此这个约束通过反面处理
f[24] - f[0] >= x // 最后24小时内雇佣人应该大于等于x个人

其中x是一个需要二分的变量，也就是最终雇佣了多少人；

而最后一个条件，可以看做是强制选x个人，那么即使实际上雇佣了小于x的人，spfa结果仍为(-)x，这样可以来判断x是否为可行解；

千辛万苦终于AC，最后迟迟难A的问题竟然是spfa中没有给vis数组赋0！这是习惯错误，因为这个spfa与平常不同的是有中途return 0，所以可能没有把vis全赋会0就退出，所以每次需要重新赋0。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
queue<int>q;
int const MAXN=40;
int T,n,r[MAXN],t[MAXN],ct,head[MAXN],L,R,dis[MAXN],cnt[MAXN];
bool vis[MAXN];
struct N{
    int to,next,w;
    N(int t=0,int n=0,int w=0):to(t),next(n),w(w) {}
}edge[MAXN*70];
bool spfa(int x)
{
    while(q.size())q.pop();
    memset(dis,0x3f,sizeof dis);
    memset(cnt,0,sizeof cnt);
    memset(vis,0,sizeof vis);//!!!
    int s=24;
    q.push(s);vis[s]=1;dis[s]=0;cnt[s]=1;
    //根据加边看到应该从后往前走，从-x人出发，dis为负 
    while(q.size())
    {
        int x=q.front();q.pop();vis[x]=0;
        if(cnt[x]>25)return 0;//若入队>25次，可判断存在负环 
        for(int i=head[x];i;i=edge[i].next)
        {
            int u=edge[i].to;
            if(dis[u]>dis[x]+edge[i].w)
            {
                dis[u]=dis[x]+edge[i].w;
                if(!vis[u])vis[u]=1,q.push(u),cnt[u]++;
            }
        }
    }
    return dis[0]==-x;//是否的确雇佣了x个人(没有被边限制卡掉) 
}
bool pd(int x)
{
    ct=0;
    memset(head,0,sizeof head);
    for(int i=1;i<8;i++)
    {
        edge[++ct]=N(i+24-8,head[i],x-r[i]);head[i]=ct;
        edge[++ct]=N(i,head[i-1],t[i]);head[i-1]=ct;
        edge[++ct]=N(i-1,head[i],0);head[i]=ct;
    
    }
    for(int i=8;i<=24;i++)
    {
        edge[++ct]=N(i-8,head[i],-r[i]);head[i]=ct;
        edge[++ct]=N(i,head[i-1],t[i]);head[i-1]=ct;
        edge[++ct]=N(i-1,head[i],0);head[i]=ct;
    }
    edge[++ct]=N(0,head[24],-x);head[24]=ct;//!f[24]-f[0]>=x
    return spfa(x);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        for(int i=1;i<=24;i++)
            scanf("%d",&r[i]);
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            int x;
            scanf("%d",&x);
            t[x+1]++;//从1~24计算 
        }
        L=0;R=n;
        int ans=-1;
        while(L<=R)
        {
            int mid=((L+R)>>1);
            if(pd(mid))ans=mid,R=mid-1;
            else L=mid+1;
        }
        if(ans!=-1)printf("%d
",ans);
        else printf("No Solution
");
    }
    return 0;
}