AOE网上的关键路径

柔情只为你懂 2022-07-14 03:46 159阅读 0赞

### AOE网上的关键路径 ###

Time Limit: 1000MS Memory Limit: 65536KB

[Submit][] [Statistic][]

#### Problem Description ####

一个无环的有向图称为无环图（Directed Acyclic Graph），简称DAG图。  
 AOE(Activity On Edge)网：顾名思义，用边表示活动的网，当然它也是DAG。与AOV不同，活动都表示在了边上，如下图所示：  
![2498.png][]![2498.png][]  
如上所示，共有11项活动（11条边），9个事件（9个顶点）。整个工程只有一个开始点和一个完成点。即只有一个入度为零的点（源点）和只有一个出度为零的点（汇点）。  
关键路径：是从开始点到完成点的最长路径的长度。路径的长度是边上活动耗费的时间。如上图所示，1 到2 到 5到7到9是关键路径（关键路径不止一条，请输出字典序最小的），权值的和为18。

#### Input ####

这里有多组数据，保证不超过10组，保证只有一个源点和汇点。输入一个顶点数n(2<=n<=10000),边数m(1<=m <=50000),接下来m行，输入起点sv，终点ev,权值w（1<=sv,ev<=n,sv != ev,1<=w <=20)。数据保证图连通。

#### Output ####

关键路径的权值和，并且从源点输出关键路径上的路径（如果有多条，请输出字典序最小的）。

#### Example Input ####

9 11
    1 2 6
    1 3 4
    1 4 5
    2 5 1
    3 5 1
    4 6 2
    5 7 9
    5 8 7
    6 8 4
    8 9 4
    7 9 2

#### Example Output ####

18
    1 2
    2 5
    5 7
    7 9

#### Hint ####

#include<iostream>
    #include<algorithm>
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<math.h>
    
    using namespace std;
    const int INF = 0;
    
    struct node
    {
        int x,y,z;
    }q[1001000];
    
    struct node1
    {
        int a,b;
    };
    
    int n,m;
    int t;
    struct node1 num[1100001];
    
    void add(int x,int y,int z)
    {
        q[t].x = x;
        q[t].y = y;
        q[t++].z = z;
    }
    
    void BF()
    {
        for(int i=0;i<=n;i++)
        {
            num[i].a = INF;
            num[i].b = -1;
        }
        num[n].a = 0;
        int flag = 0;
        for(int i=1;i<n;i++)
        {
            flag = 0;
            for(int j=0;j<t;j++)
            {
                if(num[q[j].y].a - q[j].z < num[q[j].x].a||(num[q[j].y].a-q[j].z==num[q[j].x].a&&q[j].y<num[q[j].x].b))
                {
                    num[q[j].x].a = (num[q[j].y].a - q[j].z);
                    num[q[j].x].b = q[j].y;
                    //num[q[j].y].b = q[j].x;
                    flag = 1;
                }
            }
            if(flag == 0)
            {
                break;
            }
        }
        printf("%d\n",-num[1].a);
        int xx[10100];
        memset(xx,0,sizeof(xx));
        int h = 0;
        xx[h++] = 1;
        for(int i=1;num[i].b!=n;)
        {
            i = num[i].b;
            xx[h++] = i;
        }
        xx[h] = n;
        for(int i=0;i<h;i++)
        {
            printf("%d %d\n",xx[i],xx[i+1]);
        }
    }
    
    int main()
    {
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            t = 0;
            int x,y,z;
            for(int i=0;i<m;i++)
            {
                scanf("%d%d%d",&x,&y,&z);
                add(x,y,z);
            }
            BF();
        }
        return 0;
    }

[Submit]: http://www.sdutacm.org/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/1907/pid/2498.html
[Statistic]: http://www.sdutacm.org/onlinejudge2/index.php/Home/Contest/conteststatus/cid/1907/pid/2498.html
[2498.png]: http://www.sdutacm.org/image/2498.png