poj 1275 Cashier Employment

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #define maxn 2000
  5 using namespace std;
  6 const int inf=1<<23;
  7 int r[24],t[maxn],s[maxn],dis[maxn];
  8 int n,e;
  9 int sum;
 10 struct node
 11 {
 12     int u,v,w;
 13 }p[maxn];
 14 void add(int u,int v,int w)
 15 {
 16     p[e].u=u;
 17     p[e].v=v;
 18     p[e++].w=w;
 19 }
 20 bool bellman_ford()
 21 {
 22     for(int i=0; i<=24; i++) dis[i]=inf;
 23     dis[0]=0;
 24     bool flag;
 25     for(int i=0; i<=24; i++)
 26     {
 27         flag=false;
 28         for(int j=0; j<e; j++)
 29         {
 30             if(dis[p[j].v]>dis[p[j].u]+p[j].w)
 31             {
 32                 dis[p[j].v]=dis[p[j].u]+p[j].w;
 33                 flag=true;
 34             }
 35         }
 36         if(!flag) break;
 37     }
 38     if(flag) return false;
 39     else return true;
 40 }
 41 void buil(int x)
 42 {
 43     e=48;
 44     int j;
 45     for(j=1; j<=24; j++)
 46     {
 47         int i=(j+8)%24;
 48         if(i>j)
 49         {
 50             add(i,j,-r[i]);
 51         }
 52         else if(i<j)
 53         {
 54             add(i,j,x-r[i]);
 55         }
 56     }
 57     add(24,0,-x);
 58 }
 59 
 60 
 61 void bear(int r,int l)
 62 {
 63     int low=r,high=l;
 64     while(low<=high)
 65     {
 66         //printf("%d
",sum);
 67         int mid=(low+high)/2;
 68         buil(mid);
 69         if(bellman_ford())
 70         {
 71             sum=mid;
 72             high=mid-1;
 73         }
 74         else
 75             low=mid+1;
 76     }
 77 }
 78 
 79 int main()
 80 {
 81     int m,x;
 82     scanf("%d",&m);
 83     while(m--)
 84     {
 85         for(int i=1; i<=24; i++)
 86         {
 87             scanf("%d",&r[i]);
 88         }
 89         scanf("%d",&n);
 90         memset(t,0,sizeof(t));
 91         for(int i=0; i<n; i++)
 92         {
 93             scanf("%d",&x);
 94             t[x+1]++;
 95         }
 96         e=0;
 97         for(int i=1; i<=24; i++)
 98         {
 99             add(i-1,i,t[i]);
100             add(i,i-1,0);
101         }
102         sum=-1;
103         bear(0,n);
104         if(sum==-1)
105             printf("No Solution
");
106         else
107             printf("%d
",sum);
108     }
109     return 0;
110 }
View Code