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;
}
