//hdu 1529 Cashier Employment//差分约束系统//还有国家集训队的黄源河的论文中的这题的后面两个不等式写错了//不懂差分约束可以到这看看//http://imlazy.ycool.com/post.1702305.html;//一开始看我完全没想到可以用差分约束//这题也主要是看了别人代码才过了的，还用了蹩脚的英文注释//不过真感觉这题挺神奇的//题意：//第一行t,表示有几组测试数据；第二行24个数分别表示各个小时//至少需要的出纳员数；接下去一行一个数表m示有几个应聘者//接下去有m行，每行1个数表示该应聘者的开始工作时间//每个出纳员若开始工作时间为st 则他一定连续工作8小时//即工作到 st+8 小时//思路：//根据差分约束，我们可以先找出一些看的到的不等式//s[i] 表示在从第0小时到第i个小时总的需要多少出纳员,则我们//要求的就是s[23]了；w[i]表示应聘第i个小时开始工作的出纳员数//所以我们要在输入的时候累加每个小时的应聘的出纳员数；//r[i]表示第i个小时至少需要多少出纳员//1、0 <= s[i] - s[i-1] <= w[i] (0 <= i <= 23)//2、s[i] - s[i-8] >= r[i] (8 <= i <= 23)//3、s[23] + s[i] - s[i+16] >= r[i] (0 <= i <= 7)//第一个不等式s[i]-s[i-1]表示答案中第i个小时有多少个出纳员//第二个不等式s[i]-s[i-8]表示出纳员工作的时间段有第i-8小时的人数//第三个不等式和第二个一样的意思，只是这时是跨过一天，比如工作的//的时间段有包括第1个小时的出纳员数即为 s[23]+s[1]-s[1+16]//从上面的式子看，根据差分约束，我们要找出像求最短(长)路时的//三角不等式：d[to] - d[from] >= w//我们要转化为相同的样式，也就是不等号//方向要相同，于是：上面3个式子就第一个式子需要转化，转化为//s[i] - s[i-1] >= 0 和 s[i-1]-s[i] >= -w[i]//这样子就变成4个不等式了//接下来的难点就是最后一个式子有个s[23]这个既是我们所要求的答案//这里又要当做常数(因为它的下标是固定的，当做常数比较好处理，而且//按照式子把s[23]当做常数，跟上面的样式才一样，都有变量i)，//这样我们就可以把s[23]当做常数移到右边去，然后枚举所有s[23]可能取到//的值(0 <= s[23] <= 总的应聘人数m),这里也可以用二分，不过我们尝试过//然后就可以根据三角不等式d[to]-d[from]>=w 建一条from 到 to的边//因为差分约束是求单源最短路，所以要建一个源点,我把源点的下标设为24//跟源点连边的就只要根据第1个式子跟0点建边即可(s[-1] - s[0] >= w[0])//这里s[-1]极为源点s[24]，从0指向24//求出来的dis数组中每个数就是有经过各个时间的的出纳员总数//我们用的是 >= 所以我们在求最短路是要维护好,即若s[to] - s[from] < w[i]//则要把s[to]维护为s[to] = s[from] + w[i] 这样就保持了>=号//其他的看代码中的注释//看不懂的话可以到这来看看，我也是看这的//他写的解释不错，不过跟人觉得他代码风格不好，还用goto//http://www.cnblogs.com/zhuangli/archive/2008/07/26/1252252.html#define comein freopen("in.txt", "r", stdin);#include #include #include using namespace std;#define INF 1<<30#define N 30int hour_least[N], app_st[N], hour_most[N];//count array is to count the time of a point have been visitedint head[N], relate23[N], dis[N], count[N];int eid, eid23, source_id;bool vis[N];struct EDGE{ int to, dis, next;}edge[1005];void buildMap() //build map{ eid = 0; memset(head, -1, sizeof(head)); for(int i = 1; i < 24; ++i) { //s[i] represent sum of employees at before i hour //so s[23] is the answer which us want to get //0 <= s[i] - s[i-1] <= most[i] (0 <= i <= 23) //build edge from i-1 to i for s[i] - s[i-1] >= 0 edge[++eid].to = i; edge[eid].dis = 0; edge[eid].next = head[i-1]; head[i-1] = eid; //build edge from i to i-1 for s[i-1] - s[i] >= -most[i] edge[++eid].to = i-1; edge[eid].dis = -hour_most[i]; edge[eid].next = head[i]; head[i] = eid; if(i >= 8) //s[i] - s[i-8] >= r[i] (8 <= i <= 23) { //r[i] represent at i hour need at least r[i] employees edge[++eid].to = i; edge[eid].dis = hour_least[i]; edge[eid].next = head[i-8]; head[i-8] = eid; } } //s[i-1] - s[i] >= -Num[i] (0 <= i <= 23) 这里取i=0 //s[-1] - s[0] >= -Num[0] 这里的Num相当于hour_most //from 24 to 0 edge[++eid].to = 24; edge[eid].dis = -hour_most[0]; edge[eid].next = head[0]; head[0] = eid; for(int i = 0; i < 24; ++i) { //s[23] + s[i] - s[i+16] >= r[i] (0 <= i <= 7) if(i <= 7) { //build edge from (16、17...23) to (0、1、2...7) edge[++eid].to = i; edge[eid].dis = hour_least[i] - 0; //assume s[23] zero edge[eid].next = head[i+16]; head[i+16] = eid; relate23[i] = eid; //mark the id which relate to s[23] } //Add a source point 24 //build edge from source to i, and value of edge is zero edge[++eid].to = i; edge[eid].dis = 0; //24到23的距离最长先设为0 edge[eid].next = head[24]; head[24] = eid; if(i == 23) source_id = eid; }}bool spfa(){ for(int i = 0; i < 25; ++i) { vis[i] = false; dis[i] = -(INF); count[i] = 0; } dis[24] = 0; //这个记得赋值为0，刚开始一直没找到错误，原来是这里 queue que; que.push(24); vis[24] = true; while(!que.empty()) { int now = que.front(); que.pop(); for(int i = head[now]; i != -1; i= edge[i].next) { int to = edge[i].to; if(dis[to] - dis[now] < edge[i].dis) { dis[to] = dis[now] + edge[i].dis; if(vis[to] == false) { vis[to] = true; count[to]++; //判断负环,若进队次数比边数还多，那就说明有负环 if(count[to] > eid) return false; que.push(to); } } } vis[now] = false; } return true;}void find(int n_app){ int sum = 0; bool is_find = false; while(is_find == false && sum <= n_app) { //as from point i to i+16 distanse is r[i]-s[23] //here r[i] equal to hour_least[i] and s[23] equal to sum //if s[23] too small, there will have a loop when spfa() for(int i = 0; i <= 7; ++i) //这里与最后一个不等式相关的边都要更新 edge[relate23[i]].dis = hour_least[i] - sum; //这里要更新,当最长路和sum,即从24到23的距离跟 从24到23的最长路相等 //时就表示找到答案了 edge[source_id].dis = sum; //here is most important is_find = spfa(); //寻找最长路 //听说这里sum 不能等于4 不知道为什么 不过没有加上 ||sum == 4 if(is_find == false || dis[23] != sum)//也可以过 { is_find = false; sum++; } } if(is_find == true) printf("%d\n", sum); else puts("No Solution");}int main(){ int n_case; scanf("%d", &n_case); while(n_case--) { for(int i = 0; i < 24; ++i) { hour_most[i] = 0; //记录 scanf("%d", &hour_least[i]); } int n_app; //number of applicants scanf("%d", &n_app); for(int i = 0; i < n_app; ++i) { scanf("%d", &app_st[i]); //the most applicant can reach to i hour hour_most[app_st[i]]++; } buildMap(); find(n_app); } return 0;} 
hdu 1529 Cashier Employment 差分约束系统