2015
04-10

In most recipes, certain tasks have to be done before others. For each task, if we are given a list of other tasks that it depends on, then it is relatively straightforward to come up with a schedule of tasks that satisfies the dependencies and produces a stunning dish. Many of us know that this can be solved by some algorithm called toplogical sort.

But life is not so easy sometimes. For example, here is a recipe for making pizza dough:

1.Mix the yeast with warm water, wait for 5 to 10 minutes.
2.Mix the the remaining ingredients 7 to 9 minutes.
3.Mix the yeast and the remaining ingredients together for 10 to 15 minutes.
4.Wait 90 to 120 minutes for the dough to rise.
5.Punch the dough and let it rest for 10 to 15 minutes.
6.Roll the dough.
In this case, tasks 1 and 2 may be scheduled after the first minute (we always spend the first minute to read the recipe and come up with a plan). The earliest task 3 may be started is at 8 minutes, and task 4 may start at 18 minutes after the start, and so on. This recipe is relatively simple, but if some tasks have many dependent tasks then scheduling can become unmanageable. Sometimes, the recipe may in fact be impossible to execute. For example, consider the following abstract recipe:

2.after task 1 but within 2 minutes of it, do task 2
3.at least 3 minutes after task 2 but within 2 minutes of task 1, do task 3
In this problem, you are given a number of tasks. Some tasks are related to another based on their starting times. You are asked to assign a starting time to each task to satisfy all constraints if possible, or report that no valid schedule is possible.

The input consists of a number of cases. The first line of each case gives the number of tasks n, (1 ≤ n ≤ 100). This is followed by a line containing a non-negative integer m giving the number of constraints. Each of the next m lines specify a constraint. The two possible forms of constraints are:

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

The input is terminated by n = 0.

The input consists of a number of cases. The first line of each case gives the number of tasks n, (1 ≤ n ≤ 100). This is followed by a line containing a non-negative integer m giving the number of constraints. Each of the next m lines specify a constraint. The two possible forms of constraints are:

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

The input is terminated by n = 0.

6
10
task 3 starts within 10 minutes of the starting time of task 1
task 3 starts within 9 minutes of the starting time of task 2
task 4 starts within 15 minutes of the starting time of task 3
task 5 starts within 120 minutes of the starting time of task 4
task 6 starts within 15 minutes of the starting time of task 5
3
4
task 2 starts within 2 minutes of the starting time of task 1
task 3 starts within 2 minutes of the starting time of task 1
0

3 1 8 18 108 118
Impossible.

这是一道查分约束方程的题。难点在于如何建图，task i starts at least A minutes later than task j得到的方程是：tj – ti <= -Ａ，task i starts within A minutes of the starting time of task j得到的方程是： tj – ti <= 0和ti – tj <= A，然后建图，最后用bellman_ford来判，注意输出时，为防止时间有负数或超出1000000，每个数要减去最小的数并加1。

#include<iostream>
#include<cstdio>
#include<string>
#include<cctype>
#include<sstream>
using namespace std;
#define MAXN 110
#define INF (1 << 30)
int d[MAXN], u[MAXN * MAXN], v[MAXN * MAXN], w[MAXN * MAXN];
int e, n, vMin, num[4];
int ballman_ford()
{
for(int i = 0; i <= n; d[i++] = INF);
d[0] = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < e; j++){
if(d[v[j]] > d[u[j]] + w[j])
d[v[j]] = d[u[j]] + w[j];
}
}
for(int i = 0; i < e; i++)
if(d[v[i]] > d[u[i]] + w[i])
return 0;
vMin = (1 << 30);
for(int i = 1; i <= n; i++)
if(vMin > d[i]) vMin = d[i];
return 1;
}
int main()
{
string input, s;
int i, j, k, l, m, flag;
//freopen("input.txt", "r", stdin);
while(scanf("%d", &n)){
if(!n) break;
scanf("%d", &m);
cin.ignore();
e = 0;
for(i = 0; i < m; i++){
getline(cin, input);
istringstream in (input);
//cout<<input<<endl;
num[0] = num[1] = num[2] = 0;
for(j = 0, l = 0; in>>s; j++){
if(isdigit(s[0])){
for(k = 0; k < s.size(); k++)
num[l] = num[l] * 10 + s[k] - '0';
l++;
}
if(j == 3){
if(s == "at") flag = 1;
else flag = 0;
}
}
if(flag){
u[e] = num[0]; v[e] = num[2]; w[e++] = -num[1];
}else {
u[e] = num[0]; v[e] = num[2]; w[e++] = 0;
u[e] = num[2]; v[e] = num[0]; w[e++] = num[1];
}
}
for(i = 1; i <= n; e++, i++){
u[e] = 0; v[e] = i; w[e] = 0;
if(ballman_ford()){
for(i = 1; i <= n; i++)
printf("%d%c", d[i] - vMin + 1, i == n ? '/n' : ' ');
}else printf("Impossible./n");
}
return 0;
}