hdu 1534(差分约束)

题意：

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

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

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

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

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

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

解题思路：由于每个点之间具有约束关系，可采用差分约束

SAS u,v  S[u]>=S[v];
SAF u,v  S[u]>=S[v]+D[v];
FAF u,v  S[u]+D[u]>=S[v]+D[v];
FAS u,v  S[u]+D[u]>=S[v];

AC:

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define INF 1e8
#define MAXN 10005
using namespace std;

struct edge
{
    int u,v,w,next;
}E[200000];
int head[MAXN],ecnt,N,cas;
int dis[MAXN],D[MAXN],cnt[MAXN];
bool vis[MAXN];
queue<int>Q;

void Insert(int u,int v,int w)
{
    E[ecnt].u=u;
    E[ecnt].v=v;
    E[ecnt].w=w;
    E[ecnt].next=head[u];
    head[u]=ecnt++;
}

void Init()
{
    int i,u,v,w;
    char s[20];
    memset(head,-1,sizeof(head)); 
	ecnt=0;
    for(i=1;i<=N;i++)
        scanf("%d",&D[i]);
    while(scanf("%s",s)!=EOF)//建图
    {
        if(s[0]=='#') break;
        scanf("%d%d",&u,&v);
        if(strcmp(s,"SAS")==0)
            Insert(v,u,0);
        else if(strcmp(s,"SAF")==0)
            Insert(v,u,D[v]);
        else if(strcmp(s,"FAF")==0)
            Insert(v,u,D[v]-D[u]);
        else
            Insert(v,u,-D[u]);
    }
    for(i=1;i<=N;i++)//保证每个点都被扩展到
        Insert(0,i,0);
}

bool SPFA()
{
    int i,u,v,w;
    while(!Q.empty()) Q.pop();
    memset(vis,false,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    for(i=0;i<=N;i++)
        dis[i]=-INF;
    Q.push(0);
    dis[0]=0;
    vis[0]=true;
    while(!Q.empty())
    {
        u=Q.front();Q.pop();
        vis[u]=false;
        cnt[u]++;
        if(cnt[u]>N) return false;
        for(i=head[u];i!=-1;i=E[i].next)
        {
            v=E[i].v;w=E[i].w;
            if(dis[v]<dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!vis[v])
                {
                    Q.push(v);
                    vis[v]=true;
                }
            }
        }
    }
    return true;
}

void Solve()
{
    int i;
    printf("Case %d:\n",cas++);
    if(!SPFA())
        printf("impossible\n");
    else
    {
        for(i=1;i<=N;i++)
            printf("%d %d\n",i,dis[i]);
    }
    printf("\n");
}

int main()
{
    cas=1;
    while(scanf("%d",&N),N)
    {
        Init();
        Solve();
    }
	return 0;
}