Hdu 1534 【差分约束系统】.cpp

题意：

　　安排计划，有4种约束方式，给出你这些时间的n个约束..

　　如果计划是可行的，求出每一件事发生的最早时间..否则输出“impossible”..

　　①. FAF a b a要在b完成后完成..

　　②. FAS a b a要在b开始前完成..

　　③. SAS a b a要在b开始前开始..

　　④. SAF a b a要在b结束前开始..

思路：

　　 简述差分约束系统..

　　差分约束系统就是给出一个不等式组..每个不等式形如 xj-xi <= bk bk是一些已知的常量..

　　求出所有未知量xi..

　　***---要注意是小于等于---***

　　其实差分约束系统就像是最短路中的松弛条件：dj-di <= G[i][j]

　　所有其实差分约束系统就是这么求的..

　　根据给出的条件自己创建满足条件的不等式..然后就可以求出答案了..

　　这道题根据给出的约束条件，设置dis[i]表示第i件事发生的最早时间..

　　就可以知道建图应该怎么建了..

　　代码中给出了注释..　　

Tips：

　　建图的时候以边为根据建..

　　边的结构体中有起点，终点和权值..

　　然后用Bellman-Ford遍历每一条边的每一种情况..

　　/*我记得当时做题的时候没有用邻接表和邻接矩阵是有原因的..但是现在忘了..想起来的时候再补充上..*/

　　注意所有入度为0的点都是没有被要求在别的时间发生后发生的事件..所以他们发生的时间就是0

Code：

  1 #include <stdio.h>
  2 #include <cstring>
  3 #include <stdio.h>
  4 #include <queue>
  5 #include <algorithm>
  6 using namespace std;
  7 
  8 const int MAXN = 1010;
  9 const int MAXM = 1000000;
 10 const int INF = 0x1f1f1f1f;
 11 
 12 struct Edge
 13 {
 14     int from;
 15     int to;
 16     int w;
 17 }edge[MAXM];
 18 int tot;
 19 
 20 void add(int s, int u, int w)
 21 {
 22     edge[tot].from = s;
 23     edge[tot].to = u;
 24     edge[tot].w = w;
 25     tot++;
 26 }
 27 
 28 int arr[MAXN], a, b, dis[MAXN], in[MAXN];
 29 int main()
 30 {
 31    // freopen("in.txt", "r", stdin);
 32     int n, iCase = 0;
 33     char ord[10];
 34     bool flag;
 35     while (~scanf("%d", &n)) {
 36         if (n == 0) break;
 37 
 38         iCase++;
 39         printf("Case %d:\n", iCase);
 40         memset(dis, INF, sizeof(dis));
 41         memset(in, 0, sizeof(in));
 42         tot = 0;
 43         flag = true;
 44 
 45         for (int i = 0; i < n; ++i)
 46             scanf("%d", &arr[i]);
 47         scanf("%s", ord);
 48         while (ord[0] != '#') {
 49             scanf("%d %d", &a, &b);
 50             a--, b--;
 51             in[b]++;
 52             if (strcmp(ord, "SAS") == 0) {  //如果是SAS..就G[a][b] = 0;
 53                 add(a, b, 0);
 54             } else if (strcmp(ord, "SAF") == 0) {  //如果是SAF..就是G[a][b] = -arr[b];
 55                 add(a, b, -arr[b]);
 56             } else if (strcmp(ord, "FAF") == 0) {  //如果是SAF..就是G[a][b] = arr[a]-arr[b];
 57                 add(a, b, arr[a]-arr[b]);//!
 58             } else {
 59                 add(a, b, arr[a]);  //如果是SAF..就是G[a][b] = arr[a];
 60             }
 61             scanf("%s", ord);
 62         }
 63 
 64         queue<int> Q;
 65         for (int i = 0; i < n; ++i) {
 66             if (in[i] == 0) {
 67                 dis[i] = 0;
 68             }
 69             Q.push(i);
 70             in[i] = 1;
 71         }
 72 
 73         for (int i = 0; i < n-1; ++i)
 74             for (int j = 0; j < tot; ++j) {
 75                 int from = edge[j].from, to = edge[j].to, w = edge[j].w;
 76                     if (dis[to] > dis[from]+w)
 77                         dis[to] = dis[from]+w;
 78             }
 79         for (int i = 0; i < tot; ++i) {
 80             int from = edge[i].from, to = edge[i].to, w = edge[i].w;
 81                 if (dis[to] > dis[from]+w) {
 82                     flag = false;
 83                     break;
 84                 }
 85         }
 86 
 87 /*
 88         while (!Q.empty()) {
 89             int id = Q.front();
 90             Q.pop();
 91             for (int i = 0; i < n; ++i)
 92                 if (i != id && dis[id]+G[id][i] < dis[i]) {
 93                     dis[i] = dis[id]+G[id][i];
 94                     in[i]++;
 95                     if (in[i] > n) {
 96                         flag = false;
 97                         goto loop;
 98                     }
 99                     Q.push(i);
100                 }
101         }
102 */
103       //  loop:
104         if (flag) {
105             int minDis = INF;
106             for (int i = 0; i < n; ++i)
107                 minDis = min(minDis, dis[i]);
108             for (int i = 0; i < n; ++i)
109                 printf("%d %d\n", i+1, dis[i]-minDis);
110         } else puts("impossible");
111         puts("");
112     }
113     return 0;
114 }

View Code

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1534