Problem Description

说明： AOE 网络是有向无环加权图，其中顶点表示事件，弧表示活动，权表示活动持续的时间，通常可以用来估算工程完成的时间，即图中从开始点到结束点之间最长的路径对应的时间。请完成一个程序，完成下列任务：
1 、计算 AOE 网络对应的拓扑排序。如果排序结果不唯一，请输出按照从小到大的顺序排列的结果。从小到大的顺序就是输入的节点序列顺序（参见下面关于输入格式的说明）。如图1中满足要求的拓扑排序是： a-b-c-d-e-f-g-h-k ,图2中满足要求的拓扑排序是：v1-v3-v5-v2-v6-v4-v7-v8-v9
2 、计算 AOE 网络的关键路径。注意关键路径可能不唯一，要求输出所有的关键路径。同样，按照是按照从小到大的顺序输出。例，如果得到两条关键路径，分别是0-1-3-6-8-9和0-1-3-4-5-8-9，那么先输出后一条路径，因为两条路径中前三个节点相同，而后一条路径第四个节点的编号小。
测试用例的输入输出格式说明：
输入：

节点的个数，边的条数；
各个节点的名称序列
边： < 起点 , 终点 , 权值 > 。说明起点和终点是在各个点在输入序列中的位置，如图1中边 <a,b> 表示为 <0,1,6> 。

输出：

拓扑排序；
关键路径

测试用例1是与图1相对应的，测试用例2是与图2相对应的。

图1
图2

---

测试输入1

9,11
a,b,c,d,e,f,g,h,k,
<0,1,6>,<0,2,4>,<0,3,5>,<1,4,1>,<2,4,1>,<4,6,8>,<4,7,7>,<3,5,2>,<5,7,4>,<6,8,2>,<7,8,4>

测试输出1

a-b-c-d-e-f-g-h-k
a-b-e-h-k

---

测试输入2

9,11
v1,v2,v3,v4,v5,v6,v7,v8,v9,
<0,4,6>,<0,2,4>,<0,5,5>,<4,1,1>,<2,1,1>,<1,6,8>,<1,7,7>,<5,3,2>,<3,7,4>,<6,8,2>,<7,8,4>

测试输出2

v1-v3-v5-v2-v6-v4-v7-v8-v9
v1-v5-v2-v8-v9

---

AcCode

//
//  main.cpp
//  计算工程完成的关键路径
//
//  Created by jetviper on 2017/3/26.
//  Copyright © 2017年 jetviper. All rights reserved.
//

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int n,b,k;
struct{
    char name[10];
    int innum;
    int outnum;
    int linkto[5000];
    int value[5000];
}node[600];
char temp[5000];
void scanfb(char *temp,int f,int *get){
    char s1[20],s2[20],s3[20];
    int p,s,c;
    int len = strlen(temp);
    if(temp[f]=='<'){
        p=0;
        for(int j=f+1;j<len;j++){
            if(temp[j]!=','){
                s1[p++]=temp[j];
            }
            else{
                s1[p]='\0';
                s=j;
                break;
            }
        }
        p=0;
        for(int j=s+1;j<len;j++){
            if(temp[j]!=','){
                s2[p++]=temp[j];
            }
            else{
                s2[p]='\0';
                c=j;
                break;
            }
        }
        p=0;
        for(int j=c+1,p=0;j<len;j++){
            if(temp[j]!=','){
                s3[p++]=temp[j];
            }
            else{
                s3[p]='\0';
                break;
            }
        }
    }
    get[0]=atoi(s1);
    get[1]=atoi(s2);
    get[2]=atoi(s3);
}

int aoevsd[1000] = {0};
int list[100],q,res[100],p;

void AOEsearch(){
    
    if(q==0)return;
    else {
        int now = list[q];
        res[++p] = list[q--];
        
        for(int i=0;i<node[now].outnum;i++){
            node[node[now].linkto[i]].innum--;
            if(node[node[now].linkto[i]].innum == 0){
                list[++q] = node[now].linkto[i];
            }
        }
        for(int i=1;i<=q;i++)
            for(int j=i;j<=q;j++){
                if(list[j]>list[i]){
                    int temp = list[i];
                    list[i] = list[j];
                    list[j] = temp;
                }
            }     
        AOEsearch(); 
    }  
}

int road[100][100]={0};
int maxvalue=0,roadnum=0;
char  resroad[100][500];
int start;
void searchMain(char lastroad[100],int cout,int now){
    char sasa[100];
    strcpy(sasa,lastroad);
    if(now!=start)strcat(sasa,"-");
    strcat(sasa,node[now].name);
    if(cout > maxvalue){
        maxvalue = cout;
        roadnum = 1;
        strcpy(resroad[roadnum],sasa);
        
    }
    else if(cout == maxvalue){
        roadnum++;
        strcpy(resroad[roadnum],sasa);
        
    }
    
    for(int i=0;i<node[now].outnum;i++){
        searchMain(sasa,cout + node[now].value[i], node[now].linkto[i]);
    }   
}
int main() {
    char str[1000];
    int get[6];
    
    scanf("%d,%d",&n,&b);
    
    for(int i=0;i<n;i++){
        node[i].outnum = 0;
        node[i].innum = 0;
    }
    
    
    scanf("%s",str);
    k=0;
    int qtemp=0;
    for(int i=0;i<strlen(str);i++){
        if(str[i]!=','){
            node[k].name[qtemp++]=str[i];
        }
        else {
            node[k].name[qtemp]='\0';
            k++;
            qtemp=0;
        }
        
    }
    
    scanf("%s",temp);
    for(int i=0;i<strlen(temp);i++){
        if(temp[i]=='<'){
            scanfb(temp,i,get);
            node[get[0]].value[node[get[0]].outnum] = get[2];
            node[get[0]].linkto[node[get[0]].outnum++] = get[1];
            node[get[1]].innum++;
        }
    }
    //sort linktos and values
    for(int i=0;i<n;i++){
        for(int j=0;j<node[i].outnum;j++){
            for(int k=j;k<node[i].outnum;k++){
                if(node[i].linkto[j]>node[i].linkto[k]){
                    int tp1 = node[i].linkto[j];
                    int tp2 = node[i].value[j];
                    node[i].linkto[j] = node[i].linkto[k];
                    node[i].value[j] = node[i].value[k];
                    node[i].linkto[k] = tp1;
                    node[i].value[k] = tp2;
                }
            }
        }
    }
    //start
    
    q=0;
    p=0;
    for(int i=0;i<n;i++){
        if(node[i].innum==0){
            list[++q] = i;
        }
    }
    
    AOEsearch();
    if(p==n){
        printf("%s",node[res[1]].name);
        for(int i=2;i<=p;i++)printf("-%s",node[res[i]].name);
        printf("\n");
        start = res[1];
        searchMain("",0,start);
        
        
        for(int i=1;i<=roadnum;i++){
            printf("%s\n",resroad[i]);
        }
        
    }
    else {
        printf("NOT OPOLOGICAL PATH\n");
    }
    
    return 0;
}