题目描述
<p class="p0"> <span style="font-size:10.5000pt;font-family:'宋体';">描述：</span><span style="font-size:10.5000pt;font-family:'宋体';"></span> </p> <p class="p0"> <span style="font-size:10.5000pt;font-family:'宋体';"> 图的连接边上的数据表示其权值，带权值的图称作网。</span><span style="font-size:10.5000pt;font-family:'宋体';"></span> </p> <p> <img src="http://tk.hustoj.com/attached/image/20140706/20140706190954_57266.png" alt="" /> </p> <p> <br /> </p> <p class="p0" style="text-indent:18.5850pt;text-align:left;"> <span style="font-size:10.5000pt;font-family:'宋体';">上图可描述为顶点集为</span><span style="font-size:10.5000pt;font-family:'Arial';">（<span>a,b,c,d,e)</span></span><span style="font-size:10.5000pt;font-family:'Arial';"></span> </p> <p class="p0" style="text-indent:18.5850pt;text-align:left;"> <span style="font-size:10.5000pt;font-family:'宋体';">边集及其权值为(始点，终点 权值）：</span><span style="font-size:10.5000pt;font-family:'Arial';">a b 3</span><span style="font-size:10.5000pt;font-family:'Arial';"></span> </p> <p class="p0" style="margin-left:147.0000pt;text-indent:21.0000pt;text-align:left;"> <span style="font-size:10.5000pt;font-family:'Arial';"> a c 2 </span><span style="font-size:10.5000pt;font-family:'Arial';"></span> </p> <p class="p0" style="margin-left:147.0000pt;text-indent:21.0000pt;text-align:left;"> <span style="font-size:10.5000pt;font-family:'Arial';"> b d 5</span><span style="font-size:10.5000pt;font-family:'Arial';"></span> </p> <p class="p0" style="margin-left:147.0000pt;text-indent:21.0000pt;text-align:left;"> <span style="font-size:10.5000pt;font-family:'Arial';"> c d 7</span><span style="font-size:10.5000pt;font-family:'Arial';"></span> </p> <p class="p0" style="text-indent:18.5850pt;text-align:left;"> <span style="font-size:10.5000pt;font-family:'Arial';"> c e 4</span><span style="font-size:10.5000pt;font-family:'Arial';"></span> </p> <p class="p0" style="text-indent:18.5850pt;text-align:left;"> <span style="font-size:10.5000pt;font-family:'Arial';"> d e 6</span><span style="font-size:10.5000pt;font-family:'Arial';"> </span><span style="font-size:10.5000pt;font-family:'Arial';"> </span><span style="font-size:10.5000pt;font-family:'宋体';"> </span><span style="font-size:10.5000pt;font-family:'宋体';"></span> </p> <p class="p0" style="background:#FFFFFF;"> <span style="font-size:10.5000pt;font-family:'宋体';"> </span><span style="font-size:10.5000pt;font-family:'宋体';">网的源点是入度为0的顶点，汇点是出度为0的顶点。网的关键路径是指</span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'Arial';background:#FFFFFF;">从源点到汇点的所有路径中，具有最大路径长度的路径</span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;">。上图中的关键路径为</span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;">a->c->d->e<span>，其权值之和为关键路径的长度为</span><span>15</span><span>。</span></span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;"></span> </p> <p class="p0" style="background:#FFFFFF;"> <span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;"> 本题的要求是根据给出的网的邻接矩阵求该网的关键路径及其长度。</span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;"></span> </p> <span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;"></span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;"></span> <p> <br /> </p>
输入格式
<p class="p0" style="background:#FFFFFF;"> <span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;">第一行输入一个正整数<span>n</span><span>（</span><span>1<=n<=5)</span><span>，其代表测试数据数目，即图的数目</span></span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;"></span> </p> <p class="p0" style="background:#FFFFFF;"> <span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;">第二行输入<span>x(1<=x<=15)</span><span>代表顶点个数，</span><span>y(1<=y<=19)</span><span>代表边的条数</span></span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;"></span> </p> <p class="p0" style="background:#FFFFFF;"> <span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;">第三行给出图中的顶点集，共<span>x</span><span>个小写字母表示顶点</span></span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;"></span> </p> <span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;">接下来每行给出一条边的始点和终点及其权值，用空格相隔，每行代表一条边。</span><br />
输出格式
<p class="p0" style="background:#FFFFFF;"> <span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;">第一个输出是图的关键路径（用给出的字母表示顶点， 用括号将边括起来，顶点逗号相隔）</span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;"></span> </p> <p class="p0" style="background:#FFFFFF;"> <span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;">第二个输出是关键路径的长度</span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;"></span> </p> <p class="p0" style="background:#FFFFFF;"> <span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;">每个矩阵对应上面两个输出，两个输出在同一行用空格间隔，每个矩阵的输出占一行。</span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;"></span> </p> <br />
样例
样例输入 1
2
5 6
abcde
a b 3
a c 2
b d 5
c d 7
c e 4
d e 6
4 5
abcd
a b 2
a c 3
a d 4
b d 1
c d 3
样例输出 1
(a,c) (c,d) (d,e) 15
(a,c) (c,d) 6
提交代码
请先登录后提交
🤖 AI 解题助手
DeepSeek
就绪