2013
12-12

# Schedule Problem

A project can be divided into several parts. Each part should be completed continuously. This means if a part should take 3 days, we should use a continuous 3 days do complete it. There are four types of constrains among these parts which are FAS, FAF, SAF and SAS. A constrain between parts is FAS if the first one should finish after the second one started. FAF is finish after finish. SAF is start after finish, and SAS is start after start. Assume there are enough people involved in the projects, which means we can do any number of parts concurrently. You are to write a program to give a schedule of a given project, which has the shortest time.

The input file consists a sequences of projects.

Each project consists the following lines:

the count number of parts (one line) (0 for end of input)

times should be taken to complete these parts, each time occupies one line

a list of FAS, FAF, SAF or SAS and two part number indicates a constrain of the two parts

a line only contains a ‘#’ indicates the end of a project

Output should be a list of lines, each line includes a part number and the time it should start. Time should be a non-negative integer, and the start time of first part should be 0. If there is no answer for the problem, you should give a non-line output containing "impossible".

A blank line should appear following the output for each project.

3
2
3
4
SAF 2 1
FAF 3 2
#
3
1
1
1
SAF 2 1
SAF 3 2
SAF 1 3
#
0

Case 1:
1 0
2 2
3 1

Case 2:
impossible

安排计划，有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：

#include <stdio.h>
#include <cstring>
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXN = 1010;
const int MAXM = 1000000;
const int INF = 0x1f1f1f1f;

struct Edge
{
int from;
int to;
int w;
}edge[MAXM];
int tot;

void add(int s, int u, int w)
{
edge[tot].from = s;
edge[tot].to = u;
edge[tot].w = w;
tot++;
}

int arr[MAXN], a, b, dis[MAXN], in[MAXN];
int main()
{
// freopen("in.txt", "r", stdin);
int n, iCase = 0;
char ord[10];
bool flag;
while (~scanf("%d", &n)) {
if (n == 0) break;

iCase++;
printf("Case %d:\n", iCase);
memset(dis, INF, sizeof(dis));
memset(in, 0, sizeof(in));
tot = 0;
flag = true;

for (int i = 0; i < n; ++i)
scanf("%d", &arr[i]);
scanf("%s", ord);
while (ord[0] != '#') {
scanf("%d %d", &a, &b);
a--, b--;
in[b]++;
if (strcmp(ord, "SAS") == 0) {  //如果是SAS..就G[a][b] = 0;
} else if (strcmp(ord, "SAF") == 0) {  //如果是SAF..就是G[a][b] = -arr[b];
} else if (strcmp(ord, "FAF") == 0) {  //如果是SAF..就是G[a][b] = arr[a]-arr[b];
} else {
add(a, b, arr[a]);  //如果是SAF..就是G[a][b] = arr[a];
}
scanf("%s", ord);
}

queue<int> Q;
for (int i = 0; i < n; ++i) {
if (in[i] == 0) {
dis[i] = 0;
}
Q.push(i);
in[i] = 1;
}

for (int i = 0; i < n-1; ++i)
for (int j = 0; j < tot; ++j) {
int from = edge[j].from, to = edge[j].to, w = edge[j].w;
if (dis[to] > dis[from]+w)
dis[to] = dis[from]+w;
}
for (int i = 0; i < tot; ++i) {
int from = edge[i].from, to = edge[i].to, w = edge[i].w;
if (dis[to] > dis[from]+w) {
flag = false;
break;
}
}

/*
while (!Q.empty()) {
int id = Q.front();
Q.pop();
for (int i = 0; i < n; ++i)
if (i != id && dis[id]+G[id][i] < dis[i]) {
dis[i] = dis[id]+G[id][i];
in[i]++;
if (in[i] > n) {
flag = false;
goto loop;
}
Q.push(i);
}
}
*/
//  loop:
if (flag) {
int minDis = INF;
for (int i = 0; i < n; ++i)
minDis = min(minDis, dis[i]);
for (int i = 0; i < n; ++i)
printf("%d %d\n", i+1, dis[i]-minDis);
} else puts("impossible");
puts("");
}
return 0;
}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. 这道题目的核心一句话是：取还是不取。
如果当前取，则index+1作为参数。如果当前不取，则任用index作为参数。