A - Instrction Arrangement（拓扑排序+未使用关键路径）

红太狼 2022-03-17 20:59 173阅读 0赞

### 题目描述： ###

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.

##### 题意： #####

给出一堆任务，输入三个数字x，y，z,表示完成y任务之前要完成x任务，间隔为z，每次处理要时间1，问处理完全部最少要多少时间

###### 分析： ######

本题是我刚学完拓扑的实践第一题，因为一开始并未学习关键路径，所以我一直在拓扑排序的基础之上不断的改进以求AC。在我WA了两次之后，只能看一下博客。发现好多人用的是关键路径。但是我一开始就未使用关键路径，也能过样例和自己测得一些数据。所以，我想在原代码上进行不断改进。  
刚一开始没有成绩。在我看到下面这个博客里面的测试数据之后，我WA掉了一些错误：  
[https://blog.csdn.net/u012762625/article/details/46545543][https_blog.csdn.net_u012762625_article_details_46545543]  
大家看一下这个博客里面的测试数据。  
但是，还是没有AC。于是，我在理了一遍思路。发现是自己有一个地方没有注意，改后成功AC。  
我的思路是：  
因为它是出现在拓扑排序的练习中，所以用考虑拓扑排序的思想去考虑。发现在每一个结点入度变为0（刚开始不为0的结点）的时候，我们把执行到它之前那个结点的时间加上到这个结点时间就可以了。  
例如：样例给出的格式：  
a b c  
那么我们把执行到a所需要的时间加上c就是执行到b所需要的时间。这是一个基本思路。但是当出现多个结点同时对应b的时候，那么我们需要进行判断，选取最大的。  
例如：  
a b c  
d b e  
那么在这个样例中，执行到b结点的时间是执行到a结点的时间+c和执行到d结点的时间+e。之中大的那个。  
同时注意1对多的情况：  
a b c  
a d e  
清楚了上述思路，就可以写代码了；  
AC代码：

#include"stdio.h"
    #include"string.h"
    #include"stack"
    #include"algorithm"
    using namespace std;
    typedef struct EdgeNode
    {
        int adjvex;
        int weight;
        struct EdgeNode *next;
    } EdgeNode;
    typedef struct VertexNode
    {
        int in;
        int sum;
        EdgeNode *firstedge;
    } AdjList;
    void TopoSort(AdjList Graph[],int N)
    {
        EdgeNode *e;
        int i,k,gettop;
        int top=0;
        int cnt=0;
        int sum=1;
        int maxx=0;
        stack<int> Q;
        for(int i=0; i<N; i++)
        {
            if(Graph[i].in==0)
                Q.push(i);
        }
        while(!Q.empty())
        {
            int k=Q.top();
            Q.pop();
            int Max=0;
            Max=Graph[k].sum;//将一开始要保存下来，否则会影响
            for(e=Graph[k].firstedge; e; e=e->next)
            {
                int j=e->adjvex;
                Graph[j].in--;
                if(e->weight!=0)
                {//这里是当出现1对多的时候取最大值。
                    Graph[k].sum=max(Graph[k].sum,Max+e->weight);
                    Graph[j].sum=max(Max+e->weight,Graph[j].sum);
                }
                if(Graph[j].in==0)
                {
                    Q.push(j);
                }
            }
        }
         maxx=0;
     for(int i=0;i<N;i++)//遍历找最大的 
        maxx=max(maxx,Graph[i].sum);
        printf("%d\n",maxx+1);
    }
    int main()
    {
        AdjList Graph[1001];
        int N,M;
        while(~scanf("%d%d",&N,&M))
        {
            if(N==0&&M==0)
            {
                printf("%d\n",0);continue;
            }
            for(int i=0;i<N;i++)
            {
                Graph[i].in=0;
                Graph[i].firstedge=NULL;
                Graph[i].sum=0;
            }
            for(int j=0;j<M;j++)
            {
                int a,b,c;
                scanf("%d%d%d",&a,&b,&c);
                EdgeNode *e,*pre;
                e=Graph[a].firstedge;
                pre=NULL;
                while(e!=NULL)
                {
                    pre=e;
                    e=e->next;
                }
             if(pre!=NULL)
                {
                    e=(EdgeNode *)malloc(sizeof(EdgeNode));
                    pre->next=e;
                }
             else
                {
                    e=(EdgeNode *)malloc(sizeof(EdgeNode));
                    Graph[a].firstedge=e;
                }
                e->adjvex=b;
                e->weight=c;
                e->next=NULL;
                Graph[b].in++;
            }
           /* for(int i=0;i<N;i++)
            {
                printf("i=%d ",i);
                EdgeNode *e;
                e=Graph[i].firstedge;
                while(e!=NULL)
                {
                    printf("j=%d weight=%d ",e->adjvex,e->weight);
                    e=e->next;
                }
                printf("\n");
            }*/
            TopoSort(Graph,N);
        }
    }

[https_blog.csdn.net_u012762625_article_details_46545543]: https://blog.csdn.net/u012762625/article/details/46545543