poj 1275(差分约束)

题意：1天24小时，每个小时需要售货员人r[i]个（r[1]表示从0:00-1:00,,等等），n个工人应聘，每个人开始工作时间为st[i],都工作8个小时。问最少的应聘人数。

分析：为了防止出现负数，在这里把标号设为1-24，并且设0为虚点。设x[i]是实际雇用的i时刻开始工作的员工数 ,r[i]是题目需要的i时刻正在工作的最少员工数.

设s[i] = x[1] + x[2] + …… + x[i] ,s[0]=0.
则s[i]表示1-i这段时间开始工作的员工数
再设t[i]表示i时刻开始工作的最多可以雇用的员工数
∴有0 <= x[i] <= t[i]
即 0 <= s[i] - s[i-1] <= t[i]
由于是求最小值，所以用最长路。
则有：①s[i] - s[i-1] >= 0；②s[i-1] - s[i] >= -t[i]； (1 <= i <= 24)
由于员工可以持续工作8个小时(r[i]是i时刻正在工作的最少人数)
∴x[i-7] + x[i-6] + …… + x[i] >= r[i]【i-7开始工作的人在i时刻也在工作，其他同理】
即：③s[i] - s[i-8] >= r[i] (8 <= i <= 24)
或者：(x[i+17] + …… + x[24]) + (x[1] + x[2] + …… + x[i]) >= r[i]；（i<=7）
则：s[24] - s[i+16] + s[i] >= r[i];
整理一下：④s[i] - s[i+16] >= r[i] - s[24];(1 <= i <= 7)

显然④式跟一般的差分约束式子不太一样。因为s[24]是未知的。所以我们可以去找一个④的一个充分条件来代替④式，同时使得式子是符合差分约束形式的。

即：⑤s[24] >= k

⑥s[i] - s[i+16] >= r[i] - k

显然满足①②③⑤⑥式的最小的k即为所求。枚举或二分k判断是否有正环即可。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <queue>
  7 using namespace std;
  8 
  9 const int inf = 0x3f3f3f3f;
 10 const int maxn = 25;
 11 int n;
 12 int r[maxn], t[maxn], s[maxn];
 13 struct edge
 14 {
 15     int v, c;
 16     edge(){}
 17     edge(int v, int c):v(v), c(c){}
 18 };
 19 vector <edge> adj[maxn];
 20 void build(int mid)
 21 {
 22     memset(adj, 0, sizeof(adj));
 23     for (int i = 0; i <24; ++i)
 24     {
 25         adj[i].push_back(edge(i + 1, 0));
 26         adj[i + 1].push_back(edge(i, -t[i+1]));
 27     }
 28     for (int i = 8; i <= 24; ++i)
 29     {
 30         adj[i - 8].push_back(edge(i, r[i]));
 31     }
 32     for (int i = 1; i <= 7; ++i)
 33     {
 34         adj[i+16].push_back(edge(i, r[i] - mid));
 35     }
 36     adj[0].push_back(edge(24, mid));
 37 }
 38 int dis[maxn],cnt[maxn];
 39 bool relax(int u, int v, int c)
 40 {
 41     if (dis[v] < dis[u] + c)
 42     {
 43         dis[v] = dis[u] + c;
 44         return true;
 45     }
 46     return false;
 47 }
 48 bool spfa(int src)
 49 {
 50     bool vis[maxn];
 51     memset(vis, 0, sizeof(vis));
 52     memset(cnt, 0, sizeof(cnt));
 53     for (int i = 0; i < maxn ; ++i)
 54         dis[i] = -inf;
 55     dis[src] = 0;
 56     vis[src] = 1;
 57     queue <int> q;
 58     q.push(src);
 59     while (!q.empty())
 60     {
 61         int pre = q.front();q.pop();
 62         vis[pre] = 0;
 63         for (int i = 0; i < adj[pre].size(); ++i)
 64         {
 65             if(relax(pre, adj[pre][i].v, adj[pre][i].c) && !vis[adj[pre][i].v])
 66             {
 67                 if((++cnt[adj[pre][i].v]) > 25) return false;
 68                 q.push(adj[pre][i].v);
 69                 vis[adj[pre][i].v] = 1;
 70             }
 71         }
 72     }
 73     return true;
 74 }
 75 int main()
 76 {
 77     int test;
 78     scanf("%d", &test);
 79     while(test--)
 80     {
 81         memset(r, 0, sizeof(r));
 82         memset(t, 0, sizeof(t));
 83         memset(s, 0, sizeof(s));
 84         for (int i = 1; i <= 24; ++i)
 85             scanf("%d", &r[i]);
 86         scanf("%d", &n);
 87         for (int i = 1; i <= n; ++i)
 88         {
 89             int x;
 90             scanf("%d", &x);
 91             ++t[x + 1]; 
 92         }
 93         int low = 0, high = n + 1, ans = -1;
 94         while (high >= low)
 95         {
 96             int mid = (high + low) >> 1;
 97             build(mid);
 98             if(spfa(0))
 99             {
100                 ans = mid;
101                 high = mid - 1;
102             }
103             else
104                 low = mid + 1;
105         }
106         /*for (int i = 0; i <= n; ++ i)
107         {
108             build(i);
109             //cout<<i<<endl;
110             if(spfa(0))
111             {
112                 ans = i;
113                 break;
114             }
115         }*/
116         if(ans == -1)
117             printf("No Solution\n");
118         else
119             printf("%d\n", ans);
120     }
121     return 0;
122 }