题目链接：点击打开链接

题意：

有n个任务 m个限制条件

1、task i starts at least A minutes later than task j

表示 i - j >= A

2、task i starts within A minutes of the starting time of task j

表示 i - j <= A

问：每个任务开始的时间。 求一个任意解

思路：

差分约束，对于不等式形如：

点u，v ： 常数C

有： u - v <= C

则从v->u 连一条长度为C的边。

若有负环则差分约束无解。否则就能求得一个任意解。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; #define inf 100000000 #define N 200 #define M 200005 struct node{ int from, to, dis, nex; }edge[M]; int head[N], edgenum; void init(){memset(head, -1, sizeof head); edgenum = 0;} void add(int u, int v, int d){ node E = {u, v, d, head[u]}; edge[edgenum] = E; head[u] = edgenum++; } int n, m; int dis[N], inq[N], tim[N]; bool spfa(){ memset(tim, 0, sizeof tim); memset(inq, 0, sizeof inq); dis[0] = 0; for(int i = 1; i <= n; i++) { dis[i] = inf; add(0, i, 0); } queue
        
         q; q.push(0); while(!q.empty()) { int u = q.front(); q.pop(); inq[u] = 0; for(int i = head[u]; ~i; i = edge[i].nex) { int v = edge[i].to; if(dis[v] > dis[u] + edge[i].dis) { dis[v] = dis[u] + edge[i].dis; if(!inq[v]) { inq[v] = 1; tim[v]++; q.push(v); if(tim[v]>n)return false; } } } } return true; } char s[100]; void eat(int x){while(x--)scanf("%s",s);} void build(){ scanf("%d", &m); init(); int a, b, x, i; while(m--) { eat(1); scanf("%d", &a); eat(2); if(s[0] == 'a') { eat(1); scanf("%d", &x); eat(4); scanf("%d", &b); add(a, b, -x); } else { scanf("%d", &x); eat(7); scanf("%d", &b); add(b, a, x); } add(a, b, 0); } } void solve(){ build(); if(spfa() == false) { puts("Impossible."); return ;} int minn = dis[1]; for(int i = 2; i <= n; i++) minn = min(minn, dis[i]); minn = -minn +1; for(int i = 1; i <= n; i++) printf("%d%c", dis[i]+minn, i==n?'\n':' '); } int main() { int a, b, x, i; while(scanf("%d", &n), n){ solve(); } return 0; } /* 2 2 task 1 starts at least 5 minutes later than task 2 task 1 starts within 5 minutes of the starting time of task 2 2 2 task 1 starts at least 6 minutes later than task 2 task 1 starts within 5 minutes of the starting time of task 2 2 2 task 1 starts at least 5 minutes later than task 2 task 1 starts within 6 minutes of the starting time of task 2 2 2 task 2 starts at least 5 minutes later than task 1 task 1 starts within 5 minutes of the starting time of task 2 2 2 task 2 starts at least 0 minutes later than task 1 task 1 starts within 0 minutes of the starting time of task 2 ans: */