Login Register

🚫

违规Action检测

禁止Use右键菜单

⚠️ 此Action已被系统记录

1

关键路径

📝 Solutions 🔵 仅限 C++

Problems Description

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

Input格式

<p class="p0" style="background:#FFFFFF;"> <span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;">Page 一行输入一items正整数<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;">Page 二行输入<span>x(1<=x<=15)</span><span>代表顶点items数，</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;">Page 三行给出图中的顶点集，Total<span>x</span><span>items小写字母表示顶点</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 />

Output格式

<p class="p0" style="background:#FFFFFF;"> <span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;">Page 一items输出是图的关键路径（用给出的字母表示顶点，用括号将边括起来，顶点逗号相隔）</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;">Page 二items输出是关键路径的长度</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;">每items矩阵对应上面两items输出，两items输出在同一行用空格间隔，每items矩阵的输出占一行。</span><span style="color:#333333;font-weight:normal;font-style:normal;font-size:10.5000pt;font-family:'宋体';background:#FFFFFF;"></span> </p> <br />

Sample

Sample Input 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

Sample Output 1

(a,c) (c,d) (d,e) 15 (a,c) (c,d) 6

Submit Code

请先Login后Submit

🤖 AI 解题助手

OpenRouter

就绪

👋 你好！我是 AI 解题助手。
我已阅读了这problems题，可以帮你points析思路、提供Code示例。
🔓 完全Free · 无需消耗 Token