Instrction Arrangement (hdu 4109 差分约束)

Instrction Arrangement

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1395    Accepted Submission(s): 584

Problem Description

Ali has taken the Computer Organization and Architecture course this term. He learned that there may be dependence between instructions, like WAR (write after read), WAW, RAW.

If the distance between two instructions is less than the Safe Distance, it will result in hazard, which may cause wrong result. So we need to design special circuit to eliminate hazard. However the most simple way to solve this problem is to add bubbles (useless
operation), which means wasting time to ensure that the distance between two instructions is not smaller than the Safe Distance.

The definition of the distance between two instructions is the difference between their beginning times.

Now we have many instructions, and we know the dependent relations and Safe Distances between instructions. We also have a very strong CPU with infinite number of cores, so you can run as many instructions as you want simultaneity, and the CPU is so fast that
it just cost 1ns to finish any instruction.

Your job is to rearrange the instructions so that the CPU can finish all the instructions using minimum time.

Input

The input consists several testcases.

The first line has two integers N, M (N <= 1000, M <= 10000), means that there are N instructions and M dependent relations.

The following M lines, each contains three integers X, Y , Z, means the Safe Distance between X and Y is Z, and Y should run after X. The instructions are numbered from 0 to N - 1.

Output

Print one integer, the minimum time the CPU needs to run.

Sample Input

5 2
1 2 1
3 4 1

Sample Output

2

Hint

In the 1st ns, instruction 0, 1 and 3 are executed;
In the 2nd ns, instruction 2 and 4 are executed.
So the answer should be 2.

Source

2011 Alibaba-Cup Campus Contest

Recommend

lcy   |   We have carefully selected several similar problems for you:  4103 4105 4104 4101 4102

题意:安排n个任务在CPU上工作,告诉m个限制,u,v,z表示v必须在u指令之后执行,并且u和v之间要间隔z秒,问把所有的任务完成最少时间为多少。

思路:差分约束系统,由题意:dist[v]-dist[u]>=z,变形得:dist[u]<=dist[v]-z,根据这个建图v->u权为-z,源点到i权为0,i到汇点权为-1,然后求最短路,答案为 -dist[n+1].

代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
const int INF=0x3f3f3f3f;
typedef long long LL;

const int MAXM = 100000;
const int MAXN = 1005;

struct Edge
{
    int u,v,len,next;
}edge[MAXM];

int n,m,num;
int head[MAXN],dist[MAXN],inq[MAXN];

void init()
{
    num=0;
    memset(head,-1,sizeof(head));
}

void addedge(int u,int v,int len)
{
    edge[num].u=u;
    edge[num].v=v;
    edge[num].len=len;
    edge[num].next=head[u];
    head[u]=num++;
}

void spfa()
{
    memset(dist,INF,sizeof(dist));
    memset(inq,0,sizeof(inq));
    inq[0]=1;
    dist[0]=0;
    queue<int>Q;
    Q.push(0);
    while (!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        inq[u]=0;
        for (int i=head[u];~i;i=edge[i].next)
        {
            int v=edge[i].v;
            if (dist[v]>dist[u]+edge[i].len)
            {
                dist[v]=dist[u]+edge[i].len;
                if (!inq[v])
                {
                    inq[v]=1;
                    Q.push(v);
                }
            }
        }
    }
    printf("%d\n",-dist[n+1]);
}

int main()
{
    int i,j,u,v,w;
    while (~scanf("%d%d",&n,&m))
    {
        init();
        for (i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            u++,v++;
            addedge(v,u,-w);
        }
        for (i=1;i<=n;i++)
        {
            addedge(0,i,0);
            addedge(i,n+1,-1);
        }
        spfa();
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

时间: 08-24

Instrction Arrangement (hdu 4109 差分约束)的相关文章

hdu 1364(差分约束)

King Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 12056   Accepted: 4397 Description Once, in one kingdom, there was a queen and that queen was expecting a baby. The queen prayed: ``If my child was a son and if only he was a sound kin

Hdu 3666 THE MATRIX PROBLEM(差分约束)

题目地址:http://acm.split.hdu.edu.cn/showproblem.php?pid=3666 思路:差分约束. 取对数将乘除转化为加减. L<=m[i][j]*a[i]/b[j]<=U log(L/m[i][j])<=log(a[i])-log(b[j])<=log(U/m[i][j]) 则 : log(a[i])<=log(b[j])+log(U/m[i][j]) log(b[j])<=log(a[i])+log(m[i][j]/L) SPFA判

Hdu 4594 Difference(奇圈判断+差分约束)

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=4598 思路:由题意可知两相连点ai符号一定相反,所以若存在奇圈则一定无解.染色,colour[i]==1表示为正,colour[i]==2表示为负.由于(b)条件为充要条件,所以对于图中的点| a[i]-a[j] | >= T,对于非图中点| a[i]-a[j] | < T,即| a[i]-a[j] | <= T-1 .所以图中点,若colour[i]==1,a[i]-a[j] >=

poj2983——差分约束,bellman_ford

poj2983——差分约束,bellman_ford Is the Information Reliable? Time Limit: 3000MS   Memory Limit: 131072K Total Submissions: 11560   Accepted: 3658 Description The galaxy war between the Empire Draco and the Commonwealth of Zibu broke out 3 years ago. Draco

差分约束

1.bzoj3436 思路: 差分约束根据限制条件建图,注意要有一个超级源点向所有点连一条边权为0的边建图看代码. 然后spfa判负环,写bfs会超时的......实测n遍. #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define inf 0x7fffffff #define ll long long #define N 100007 using na

bzoj2788 festival 差分约束

填坑中--链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2788 题意: 有$n$个正整数$X1,X2,...,Xn$,再给出$m1+m2$个限制条件,限制分为两类:1. 给出$a,b(1<=a,b<=n)$,要求满足$Xa + 1 = Xb$2. 给出$c,d (1<=c,d<=n)$,要求满足$Xc <= Xd$在满足所有限制的条件下,求集合${Xi}$大小的最大值. 首先看情况我们也知道是差分约束-- 但是这个差分

POJ 1201 Intervals 差分约束

http://poj.org/problem?id=1201 TLE了很久,因为用了cin..... 思路和其他差分约束差不多,http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html 如果区间[a, b]中至少有c个元素,如果用上面的博客,那么说明xa - xb >= c,但是注意这里是闭区间,xa - xb是不包括b这个点的, 就比如用了[a, b]有c个元素,[b, d]有x个,那么ans = c + x - 1个,

【bzoj2330】: [SCOI2011]糖果 图论-差分约束-SPFA

[bzoj2330]: [SCOI2011]糖果 恩..就是裸的差分约束.. x=1 -> (A,B,0) (B,A,0) x=2 -> (A,B,1)  [这个情况加个A==B无解的要特判] x=3 -> (B,A,0)  [恩这个是不少于一开始zz建反了] x=4 -> (B,A,1) x=5 -> (A,B,0) 然后源点到所有点建1的边[恩据说有条链所以要反着连]跑最长路就好了 1 /* http://www.cnblogs.com/karl07/ */ 2 #inc

POJ1275出纳员的雇佣【差分约束】

出纳员的雇佣 Tehran的一家每天24小时营业的超市,需要一批出纳员来满足它的需要.超市经理雇佣你来帮他解决问题:超市在每天的不同时段需要不同数目的出纳员(例如:午夜时只需一小批,而下午则需要很多)来为顾客提供优质服务.他希望雇佣最少数目的出纳员.经理已经提供你一天的每一小时需要出纳员的最少数量--R(0), R(1), ..., R(23).R(0)表示从午夜到上午1:00需要出纳员的最少数目,R(1)表示上午1:00到2:00之间需要的,等等.每一天,这些数据都是相同的.有N人申请这项工作