ZOJ1455ScheduleProblem(差分约束系统)

// 题目描述：
一个项目被分成几个部分，每部分必须在连续的天数完成。也就是说，如果某部分需要3天
才能完成，则必须花费连续的3天来完成它。对项目的这些部分工作中，
有4种类型的约束：FAS, FAF, SAF和SAS。两部分工作之间存在一个
FAS约束的含义是：第一部分工作必须在第二部分工作开始之后完成； Xa+Ta =Xb
FAF约束的含义是：第一部分工作必须在第二部分工作完成之后完成； Xa+Ta =Xb+Tb
SAF的含义是：第一部分工作必须在第二部分工作完成之后开始； Xa =Xb+Tb
SAS的含义是：第一部分工作必须在第二部分工作开始之后开始。 Xa =Xb
假定参与项目的人数足够多，也就是说可以同时作任意多的部分工作。
你的任务是编写程序，对给定的项目设计一个进度表，使得项目完成时间最短。
// 由上面的4条建立不等式建边 Xi表示i开始的时间
// 然后新建一个点 0 ，表示在所有任务完成后开始的点 那么有 X0 =Xi+T[i]
#include iostream
#include map
#include algorithm
#include queue
#include math.h
#include stdio.h
#include string.h
#include vector
using namespace std;
#define MOD 1000000007
#define maxn 21010
#define maxm 1010
struct node{
int to;
int next;
int val;
}E[maxn];
int num;
int in[maxm];
int V[maxm];
int T[maxm];
int d[maxm],cnt[maxm];
bool f[maxm];
bool sfpa(int s,int n){ // s表示起点 n表示节点个数
queue int
int u,v;
int e;
Q.push(s);
d[s]=;
f[s]=true;
while(!Q.empty()){
u=Q.front(); Q.pop();
cnt[u]++; //printf("%d ",u);
if(cnt[u] n) return false;
f[u]=false;
for(e=V[u];e!=-;e=E[e].next){
v=E[e].to;
if(d[u]+E[e].val d[v]){
d[v]=d[u]+E[e].val;
if(!f[v])
{
f[v]=true;
Q.push(v);
}
}
}
}
// printf("\n");
return true;
}
void add(char *str,int a,int b){
if(strcmp(str,"FAS")==){
E[num].to=b;
E[num].val=T[a];
E[num].next=V[a];
V[a]=num++;
}else if(strcmp(str,"FAF")==){
E[num].to=b;
E[num].val=T[a]-T[b];// printf("a=%d b=%d %d ",a,b,E[num].val);
E[num].next=V[a];
V[a]=num++;
}else if(strcmp(str,"SAF")==){
E[num].to=b;
E[num].val=-T[b];// printf("a=%d b=%d %d ",a,b,E[num].val);
E[num].next=V[a];
V[a]=num++;
}else {
E[num].to=b;
E[num].val=;
E[num].next=V[a];
V[a]=num++;
}
}
int main(){
int i,j,k;
int n;
char str[];
int Case=;
while(scanf("%d", n),n){
for(i=;i i++)
{
scanf("%d", T[i]);
V[i]=-;
d[i]=MOD;
cnt[i]=;
f[i]=false;
in[i]=;
}
i=;
V[i]=-;
d[i]=MOD;
cnt[i]=;
f[i]=false;
num=;
while(scanf("%s",str)){
if(strcmp(str,"#")==) break;
else {
scanf("%d %d", i,
in[j]=;
// printf("%s\n",str);
add(str,i,j);
}
}
for(i=;i i++){
//if(in[i])continue;
E[num].to=i;
E[num].val=-T[i];
E[num].next=V[];
V[]=num++;
}
int Min=MOD;
printf("Case %d:\n",Case++);
if(!sfpa(,n+))
printf("impossible\n");
else{
for(i=;i i++)
Min=min(Min,d[i]);//,printf("%d ",d[i]);
// if(Min==MOD){printf("impossible\n"); continue;}
for(i=;i i++)
printf("%d %d\n",i,d[i]-Min);
}
printf("\n");
}