poj1275 差分約束

   這道題很特殊，與以前做的差分約束完全不一樣，因為在它的約束條件中竟然還有變量。

建圖方法：

說明：

r[i]-------第i小時需要的人

t[i]-------第i小時去應聘的人

s[i]-------第0到i小時總共招聘的人

約束系統：

1.s[i]-s[i-1]<=t[i]

2.s[i]-s[i-1]>=0

3.s[j]-s[i]>=r[i],j=(i+8)%24,j>i

4.s[j]+sum-s[i]>=r[i],j=(i+8)%24,j

5.s[24]-s[0]>=sum

算法思想：Bellman_Ford()+枚舉sum  （此處也可以用二分枚舉，我是直接枚舉的）

[cpp]
#include  
#include  
 
using namespace std; 
struct{ 
    int u,v,w; 
}e[200]; 
int t[25],r[25],s[25],d[25]; 
int n,m; 
 
bool relax(int u,int v,int w) 
{ 
    if(d[u]+w>d[v]) 
    { 
        d[v]=d[u]+w; 
        return true; 
    } 
    return false; 
} 
 
bool Bellman_Ford() 
{ 
    int i,j; 
    bool flag=true; 
    for(i=0;i<=n;i++) 
        d[i]=100000000; 
    d[0]=0; 
    for(i=0;i     { 
        flag=false; 
        for(j=0;j             if(relax(e[j].u,e[j].v,e[j].w)) 
                flag=true; 
    } 
    if(!flag) 
        return true; 
    for(j=0;j         if(relax(e[j].u,e[j].v,e[j].w)) 
            return false; 
    return true; 
} 
 
int main() 
{ 
    int Case,sum; 
    int i,j; 
    scanf("%d",&Case); 
    while(Case--) 
    { 
        for(i=1;i<=24;i++) 
        { 
            t[i]=0; 
            scanf("%d",r+i); 
        } 
        scanf("%d",&n); 
        while(n--) 
        { 
            int time; 
            scanf("%d",&time); 
            t[time+1]++; 
        } 
        for(i=1;i<=24;i++) 
            s[i]=s[i-1]+t[i]; 
 
        ///////////////////////////  
        //此部分建固有邊  
        m=0; 
        n=24; 
        for(i=1;i<=24;i++) 
        { 
            e[m].u=i-1; 
            e[m].v=i; 
            e[m].w=0; 
            m++; 
            e[m].u=i; 
            e[m].v=i-1; 
            e[m].w=-t[i]; 
            m++; 
        } 
        for(i=1;i<=16;i++) 
        { 
            j=i+8; 
            e[m].u=i; 
            e[m].v=j; 
            e[m].w=r[j]; 
            m++; 
        } 
        //////////////////////////////  
        int mm=m; 
        for(sum=0;sum<=s[24];sum++) 
        { 
            m=mm; 
            for(i=17;i<=24;i++) 
            { 
                j=i-16; 
                e[m].u=i; 
                e[m].v=j; 
                e[m].w=r[j]-sum; 
                m++; 
            } 
            e[m].u=0; 
            e[m].v=24; 
            e[m].w=sum; 
            m++; 
            if(Bellman_Ford()) 
                break; 
        } 
        if(sum<=s[24]) 
            printf("%d\n",sum); 
        else 
            printf("No Solution\n"); 
    } 
    return 0; 
} 

#include
#include

using namespace std;
struct{
    int u,v,w;
}e[200];
int t[25],r[25],s[25],d[25];
int n,m;

bool relax(int u,int v,int w)
{
    if(d[u]+w>d[v])
    {
        d[v]=d[u]+w;
        return true;
    }
    return false;
}

bool Bellman_Ford()
{
    int i,j;
    bool flag=true;
    for(i=0;i<=n;i++)
        d[i]=100000000;
    d[0]=0;
    for(i=0;i     {
        flag=false;
        for(j=0;j             if(relax(e[j].u,e[j].v,e[j].w))
                flag=true;
    }
    if(!flag)
        return true;
    for(j=0;j         if(relax(e[j].u,e[j].v,e[j].w))
            return false;
    return true;
}

int main()
{
    int Case,sum;
    int i,j;
    scanf("%d",&Case);
    while(Case--)
    {
        for(i=1;i<=24;i++)
        {
            t[i]=0;
            scanf("%d",r+i);
        }
        scanf("%d",&n);
        while(n--)
        {
            int time;
            scanf("%d",&time);
            t[time+1]++;
        }
        for(i=1;i<=24;i++)
            s[i]=s[i-1]+t[i];

        ///////////////////////////
        //此部分建固有邊
        m=0;
        n=24;
        for(i=1;i<=24;i++)
        {
            e[m].u=i-1;
            e[m].v=i;
            e[m].w=0;
            m++;
            e[m].u=i;
            e[m].v=i-1;
            e[m].w=-t[i];
            m++;
        }
        for(i=1;i<=16;i++)
        {
            j=i+8;
            e[m].u=i;
            e[m].v=j;
            e[m].w=r[j];
            m++;
        }
        //////////////////////////////
        int mm=m;
        for(sum=0;sum<=s[24];sum++)
        {
            m=mm;
            for(i=17;i<=24;i++)
            {
                j=i-16;
                e[m].u=i;
                e[m].v=j;
                e[m].w=r[j]-sum;
                m++;
            }
            e[m].u=0;
            e[m].v=24;
            e[m].w=sum;
            m++;
            if(Bellman_Ford())
                break;
        }
        if(sum<=s[24])
            printf("%d\n",sum);
        else
            printf("No Solution\n");
    }
    return 0;
}