hdu1529(差分约束)

num[i]为从i时刻开始工作的人数

x[i] 为 i时刻实际工作的人数

r[i]为 i 时刻至少需要工作的人数

Sn表示1~n这段时间开始工作的员工数

每个时刻实际工作人数 x[i] >= 0 , 得 Si - S(i-1) >= 0

每个时刻实际工作人数 x[i] <= num[i] , 得 Si - S(i-1) <= num[i] S(i-1) - Si >= -num[i]

在 i(24>=i>=8) 时刻可以工作的人数为 x[i-7]+x[i-6]+x[i-5]+x[i-4]+x[i-3]+x[i-2]+x[i-1]+x[i] >= r[i] , 得 Si - S(i-8) >= r[i]

在i(1<=i<8)时刻可以工作的人数为 x[i-7]+x[i-6]+x[i-5]+x[i-4]+x[i-3]+x[i-2]+x[i-1]+x[i] >= r[i] ，得S(24) + Si - S(i+16) >=r[i] ;

x[1]+x[2]+...+x[24] >= 0 得到 S(24) - S0 >= 0 ;

然后用spfa求最长路

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 #include <queue>
  7 using namespace std;
  8 #define inf 9999999
  9 #define N 25
 10 #define M 1000
 11 int dis[N],vis[N],head[N],in[N];
 12 int num[N],r[N],x[N];
 13 int size,n=24,m;
 14 struct Edge
 15 {
 16     int v,w,next;
 17     Edge(){}
 18     Edge(int V,int W,int NEXT):v(V),w(W),next(NEXT){}
 19 }edge[M];
 20 void Init()
 21 {
 22     size = 0;
 23     memset(head,-1,sizeof(head));
 24 }
 25 void InsertEdge(int u,int v,int w)
 26 {
 27     edge[size] = Edge(v,w,head[u]);
 28     head[u] = size++;
 29 }
 30 bool spfa()
 31 {
 32     for(int i=0; i<=n; i++)
 33     {
 34         vis[i] = 0 ; dis[i] = -inf ; in[i] = 0;
 35     }
 36     queue<int> Q;
 37     while(!Q.empty()) Q.pop();
 38     vis[0] = 1 ; dis[0] = 0 ; in[0] = 1;
 39     Q.push(0);
 40     while(!Q.empty())
 41     {
 42         int u = Q.front();
 43         Q.pop();
 44         vis[u] = 0;
 45         for(int i=head[u]; i!=-1; i=edge[i].next)
 46         {
 47             int v = edge[i].v ;
 48             if(dis[v] < dis[u] + edge[i].w)
 49             {
 50                 dis[v] = dis[u] + edge[i].w;
 51                 if(!vis[v])
 52                 {
 53                     vis[v] = 1;
 54                     in[v]++;
 55                     if(in[v]>(n+1)) return 0;
 56                     Q.push(v);
 57                 }
 58             }
 59         }
 60     }
 61     return 1;
 62 }
 63 
 64 int main()
 65 {
 66     int T;
 67     scanf("%d",&T);
 68     while(T--)
 69     {
 70         memset(num,0,sizeof(num));
 71         for(int i=1; i<=n; i++)
 72         scanf("%d",&r[i]);
 73         scanf("%d",&m);
 74         int t;
 75         for(int i=0; i<m; i++)
 76         {
 77             scanf("%d",&t);
 78             num[t+1]++;
 79         }
 80         int left = 0 , right = m,flag=0;
 81         while(left < right)
 82         {
 83             Init();
 84             int mid = (left+right)/2;
 85             for(int i=1; i<=n; i++)
 86             {
 87                 InsertEdge(i-1,i,0); //Si - S(i-1) >= 0
 88                 InsertEdge(i,i-1,-num[i]); //S(i-1) - Si >= -num[i]
 89             }
 90             for(int i=8; i<=n; i++)
 91             InsertEdge(i-8,i,r[i]); //Si - S(i-8) >= r[i]
 92             for(int i=1; i<8; i++)
 93             InsertEdge(i+16,i,r[i]-mid); //S(24) + Si - S(i+16) >=r[i]
 94             InsertEdge(0,24,mid); //S(24) - S0 >= 0
 95             if(spfa()) //二分找最优值 
 96             {
 97                 right = mid ;
 98                 flag = 1; //标记是否有符合条件的值 
 99             }
100             else left = mid + 1;
101         }
102         if(!flag) printf("No Solution
");
103         else printf ("%d
", right);
104     }
105     return 0;
106 }

View Code