HDU 1534 Schedule Problem

应该是很明显的差分约束的题目了 只要想清楚 节点的含义 路径的含义 建好模 就好说
这里我直接设 d[I] 表示 第i个事件的开始时间
根据题意 可得

FAS：d[u]+val[u]>=d[v]
FAF：d[u]+val[u]>=d[v]+val[v]
SAF：d[u]>=d[v]+val[v]
SAS：d[u]>=d[v]

题目要求最小值，需要转化为：

d[u]–d[v]>=-val[u]
d[u]-d[v]>=val[v]-val[u]
d[u]-d[v]>=val[v]
d[u]-d[v]>=0

AC Code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cstdlib>

using namespace std;
const int maxn=100005;
const int inf=0x3f3f3f3f;
int n,idx;
int d[maxn],val[maxn],head[maxn],cnt[maxn];
bool vis[maxn];

struct node
{
    int v,w;
    int nxt;
}edge[maxn];

void init()
{
    for(int i=0;i<=n;i++)
    {
        head[i]=-1;
        d[i]=-inf;
        vis[i]=false;
        cnt[i]=0;
    }
    idx=0;
}

void add(int u,int v,int w)
{
    edge[idx].v=v;
    edge[idx].w=w;
    edge[idx].nxt=head[u];
    head[u]=idx++;
}

bool spfa()
{
    vis[0]=true;
    d[0]=0;
    queue<int> que;
    que.push(0);
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=false;
        for(int id=head[u];id!=-1;id=edge[id].nxt)
        {
            int v=edge[id].v;
            if(d[u]+edge[id].w>d[v])
            {
                d[v]=d[u]+edge[id].w;
                if(!vis[v])
                {
                    vis[v]=true;
                    que.push(v);
                    if(++cnt[v]>n) return false;
                }
            }
        }
    }
    return true;
}

int main()
{
    char ch[5];
    int u,v,cas=0;
    while(scanf("%d",&n),n)
    {
        init();
        for(int i=1;i<=n;i++) scanf("%d",val+i);
        scanf("%s",ch);
        while(ch[0]!='#')
        {
            scanf("%d %d",&u,&v);
            if(ch[0]=='S')
            {
                if(ch[2]=='S') add(v,u,0);
                else add(v,u,val[v]);
            }
            else
            {
                if(ch[2]=='S')
                    add(v,u,-val[u]);
                else add(v,u,val[v]-val[u]);
            }
            scanf("%s",ch);
        }
        printf("Case %d:\n",++cas);
        for(int i=1;i<=n;i++) add(0,i,0);
        if(spfa()) for(int i=1;i<=n;i++) printf("%d %d\n",i,d[i]);
        else puts("impossible");
        puts("");
    }
    return 0;
}