2498 数据结构实验之图论十一：AOE网上的关键路径

ゞ浴缸里的玫瑰 2022-07-14 04:41 153阅读 0赞

[AOE网上的关键路径][AOE]

#include <stdio.h>  
    #include <stdlib.h>  
    #include <string.h>  
    struct node  
    {  
       int u,v,w;  
    }edge[50010];  
    int path[50010],dis[50010],in[50010],out[50010],flag,ans;  
    int lujing(int x,int n,int ans,int m)  
    {  
        int i,j;  
        memset(path,0,sizeof(path));  
        memset(dis,0,sizeof(dis));  
        for(j=2;j<=n;j++)//控制循环次数n-1条边  
        {  
            int temp=0;  
            for(i=1;i<=m;i++)  
            {  
                if((dis[edge[i].u]+edge[i].w>dis[edge[i].v])||//到v点最大权  
                   ((dis[edge[i].u]+edge[i].w==dis[edge[i].v])&&(edge[i].u<path[edge[i].v])))//加起来相等让v的前驱是较小的点（字典序小的为先）  
                {  
                    dis[edge[i].v]=dis[edge[i].u]+edge[i].w;//dis是到v点的最大权值  
                    path[edge[i].v]=edge[i].u;//path保留v的前驱点  
                    temp=1;  
                }  
            }  
            if(temp==0)  
                break;  
        }  
        printf("%d\n",dis[ans]);  
        int k=ans;  
        while(path[k]!=0)  
        {  
           printf("%d %d\n",k,path[k]);  
           k=path[k];  
        }  
        return 0;  
    }  
    int main()  
    {  
        int n,m,i,a,b,c;  
        while(~scanf("%d%d",&n,&m))  
        {  
            memset(edge,0,sizeof(edge));  
            memset(in,0,sizeof(in));  
            memset(out,0,sizeof(out));  
           for(i=1;i<=m;i++)  
           {  
               scanf("%d%d%d",&a,&b,&c);  
               edge[i].u=b;  
               edge[i].v=a;  
               edge[i].w=c;//倒过来建  
               in[a]++;  
               out[b]++;  
           }  
           for(i=1;i<=n;i++)  
           {  
               if(in[i]==0)flag=i;//起始点  
               if(out[i]==0)ans=i;//终点  
           }  
           lujing(flag,n,ans,m);  
        }  
        return 0;  
    }

[AOE]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/1907/pid/2498