HDU 4109 Instrction Arrangement(差分约束系统)

HDU 4109 Instrction Arrangement(差分约束系统)

http://acm.hdu.edu.cn/showproblem.php?pid=4109

题意:

有N条指令的系统,该系统具有M个如下形式的依赖关系:

X Y Z,表示Y指令必须在X指令后面Z纳秒执行.

现在问你该系统的指令运行完至少需要多少纳秒?(每条指令需要运行1纳秒)

分析:

令s[x]表示第x条指令运行的时刻.

对于每条依赖关系 X Y Z,则有s[y]-s[x]>=z. 所以s[x]<= s[y]-z.则需要添加边 y到x 的权值为-z的边. 这样这些约束条件以及1到N号点就构成了一个差分约束系统了.

现在我们要求的是该系统运行完所有指令的最小时间.我们可以假设第一条指令是第0纳秒运行的,那么如果最后一条指令是第T纳秒运行的,那么运行完所有指令的时间就是T+1纳秒了.

因为我们要求的是所有可行解之间的差距尽量小,所以我们用POJ1201中介绍的第1中方案,添加一个超级源点0,使得0号点到其他点的距离为0.然后用BellmanFord算法求出一组可行解即可.然后遍历该可行解,得到指令运行的最大值max_v与最小值min_v. max_v-min_v+1 即为我们所求.

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF 1e9
using namespace std;
const int maxn =1000+10;
const int maxm =20000+10;

struct Edge
{
    int from,to,dist;
    Edge(){}
    Edge(int f,int t,int d):from(f),to(t),dist(d){}
};

struct BellmanFord
{
    int n,m;
    int head[maxn],next[maxm];
    Edge edges[maxm];
    int d[maxn];
    bool inq[maxn];

    void init(int n)
    {
        this->n=n;
        m=0;
        memset(head,-1,sizeof(head));
    }

    void AddEdge(int from,int to,int dist)
    {
        edges[m]=Edge(from,to,dist);
        next[m]=head[from];
        head[from]=m++;
    }

    void bellmanford()
    {
        memset(inq,0,sizeof(inq));
        for(int i=0;i<n;i++) d[i]= i==0?0:INF;
        queue<int> Q;
        Q.push(0);

        while(!Q.empty())
        {
            int u=Q.front(); Q.pop();
            inq[u]=false;
            for(int i=head[u];i!=-1;i=next[i])
            {
                Edge &e=edges[i];
                if(d[e.to] > d[u]+e.dist)
                {
                    d[e.to] = d[u]+e.dist;
                    if(!inq[e.to])
                    {
                        inq[e.to]=true;
                        Q.push(e.to);
                    }
                }
            }
        }
    }
}BF;
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2)
    {
        BF.init(n+1);
        while(m--)
        {
            int u,v,d;
            scanf("%d%d%d",&u,&v,&d);
            ++u,++v;
            BF.AddEdge(v,u,-d);
        }
        for(int i=1;i<=n;i++)
            BF.AddEdge(0,i,0);
        BF.bellmanford();
        int max_v=-1,min_v=INF;
        for(int i=1;i<=n;i++)
        {
            max_v=max(max_v,BF.d[i]);
            min_v=min(min_v,BF.d[i]);
        }
        printf("%d\n",max_v-min_v+1);
    }
    return 0;
}