116 lines
4.3 KiB
Markdown
116 lines
4.3 KiB
Markdown
``` cpp
|
||
|
||
A 任务排序
|
||
分数 30
|
||
作者 朱允刚
|
||
单位 吉林大学
|
||
一个工程被分解成n个子任务，编号为0至n-1。要完成整个工程需要完成所有的子任务。其中一些子任务必须先于另外一些子任务被完成。给定各子任务之间的先后关系，请编写程序给出一个合理的任务完成顺序，若工程不可行，程序亦能识别。
|
||
|
||
输入格式:
|
||
输入第一行为两个整数n和e，均不超过100。n表示子任务数。接下来e行，表示已知的两个子任务间的先后关系，每行为两个整数a和b，表示任务a必须先于任务b完成。
|
||
|
||
输出格式:
|
||
若工程不可行（一些子任务以自己为先决条件），输出“unworkable project”；若工程可行，输出为1行整数，每个整数后一个空格，为n个子任务的编号，表示子任务的完成顺序，如果有多种可能的顺序，则输出字典序最小者。
|
||
|
||
注：字典序，即对象在字典中的顺序。对于两个数字序列，从第一个数字开始比较，当某一个位置的数字不同时，该位置数字较小的序列，字典序较小，例如1 2 3 9比1 2 4 5小，1 2 8 9比1 2 10 3小。
|
||
|
||
输入样例1:
|
||
3 2
|
||
0 1
|
||
1 2
|
||
输出样例1:
|
||
0 1 2
|
||
输入样例2:
|
||
3 3
|
||
0 1
|
||
1 2
|
||
2 0
|
||
输出样例2:
|
||
unworkable project
|
||
代码长度限制
|
||
16 KB
|
||
时间限制
|
||
50 ms
|
||
内存限制
|
||
64 MB
|
||
栈限制
|
||
8192 KB
|
||
|
||
---
|
||
|
||
B 关键路径
|
||
分数 30
|
||
作者 朱允刚
|
||
单位 吉林大学
|
||
假定一个工程由若干子任务构成，使用一个包含n个顶点、e条边的AOE网表示该工程，顶点编号为1至n，有向边表示该工程的每个子任务，边的权值表示完成该子任务所需的时间，假定网中只含一个源点和一个汇点。请编写程序求出该工程的所有关键活动，并计算完成该工程所需的最短时间。
|
||
|
||
输入格式:
|
||
每个测试点包含多组测试数据。每组数据第一行为2个整数n和e，均不超过200，分别表示AOE网的顶点数和边数。接下来e行表示每条边的信息，每行为3个正整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并不一定按端点编号顺序排列，且各顶点并不一定按拓扑序排列。
|
||
|
||
输出格式:
|
||
对每组数据，若工程不可行（AOE网中存在环），输出“unworkable project”；若工程可行，则输出第一行为完成工程所需的最短时间，并从第2行开始输出关键活动，每个关键活动占一行，格式为i->j，其中i和j表示关键活动所在边的端点编号。各关键活动输出顺序为：按i的递增顺序输出，若多个关键活动的i值相同，则按j的递增顺序输出。
|
||
|
||
输入样例:
|
||
4 4
|
||
1 2 6
|
||
1 3 4
|
||
2 4 1
|
||
3 4 1
|
||
|
||
输出样例:
|
||
7
|
||
1->2
|
||
2->4
|
||
|
||
代码长度限制
|
||
16 KB
|
||
时间限制
|
||
100 ms
|
||
内存限制
|
||
64 MB
|
||
栈限制
|
||
8192 KB
|
||
|
||
---
|
||
|
||
C 最少点字典序最短路径
|
||
分数 40
|
||
作者 朱允刚
|
||
单位 吉林大学
|
||
给定一个正权有向图，图中包含n个顶点，编号为0至n-1。以顶点0作为源点，请编写程序求顶点0到各顶点的最短路径。若顶点0到某顶点存在多条最短路径，则输出经过顶点最少的那条路径，例如图1(a)中0到4的经过顶点最少的最短路径为0 - 3 - 4。若存在多条最短路径且其经过顶点个数相等，则输出字典序最小者。例如图1(b)中0到5的满足条件的最短路径为0 - 2 - 5。
|
||
|
||
g.jpg
|
||
|
||
注：字典序，即对象在字典中的顺序。对于两个数字序列，从第一个数字开始比较，当某一个位置的数字不同时，该位置数字较小的序列，字典序较小，例如1 2 3 9比1 2 4 5小，1 2 8 9比1 2 10 3小。
|
||
|
||
输入格式:
|
||
输入第一行为两个正整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过20000。接下来e行表示每条边的信息，每行为3个非负整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。
|
||
|
||
输出格式:
|
||
输出为若干行由“->”间隔的数字序列，每行为源点0到某顶点的满足条件的最短路径，如源点到某顶点无最短路径，则不输出该条路径。各条路径按终点的递增顺序输出，源点到源点的最短路径无需输出。
|
||
|
||
输入样例:
|
||
6 7
|
||
0 1 1
|
||
1 4 2
|
||
4 5 3
|
||
0 3 4
|
||
3 5 2
|
||
0 2 5
|
||
2 5 1
|
||
|
||
输出样例:
|
||
0->1
|
||
0->2
|
||
0->3
|
||
0->1->4
|
||
0->2->5
|
||
|
||
代码长度限制
|
||
16 KB
|
||
时间限制
|
||
500 ms
|
||
内存限制
|
||
20 MB
|
||
栈限制
|
||
8192 KB |