| 题目名称 | 320. [AHOI2008] 上学路线 |
|---|---|
| 输入输出 | routez.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2009-04-21加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：37， 提交：186， 通过率：19.89% | ||||
 confoo |
100 | 0.066 s | 50.32 MiB | C++ |
 Rapiz |
100 | 0.089 s | 16.73 MiB | C++ |
 ztx |
100 | 0.108 s | 10.36 MiB | C++ |
 小DOTA |
100 | 0.109 s | 18.65 MiB | C++ |
 落尘 |
100 | 0.118 s | 10.36 MiB | C++ |
|
落尘 |
100 | 0.131 s | 10.36 MiB | C++ |
 清羽 |
100 | 0.135 s | 0.33 MiB | C++ |
|
清羽 |
100 | 0.135 s | 0.33 MiB | C++ |
 asddddd |
100 | 0.138 s | 0.30 MiB | C++ |
 _Itachi |
100 | 0.138 s | 11.02 MiB | C++ |
| 本题关联比赛 | |||
| HAOI2009 模拟试题1 | |||
| HAOI2009 模拟试题1 | |||
| 防止浮躁的小练习V0.1 | |||
| 关于 上学路线 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
垃圾spj，明明我的输出和答案的顺序不一样，这都不算对......
这题有毒吧，我重测了一下，发现奇奇怪怪的全部RE了，再来一次就全部PE了...... | ||||
|
全部部分正确我也是无语了
| ||||
|
| ||||
|
好吧，我明白这道题的正确做法了，事实上我只有最后一步输出路径错了，我直接输出流量=容量的边，但实际上应该输出连接S集和T集的边。
_Itachi
2016-10-15 17:24
7楼
| ||||
|
似乎我的做法是错的，因为如果是
7 9 1 2 1 4 2 3 1 6 1 5 1 4 5 6 1 6 4 5 1 6 4 7 1 8 6 7 1 7 3 7 1 7 2 4 1 4 我跑出来是 3 4 8 1 3 6 9 但实际应该是 3 2 8 1 3 更加不可思议的是，我又试了别人过掉的代码，有对的也有不对的。。（而且大部分似乎是一毛一样的） 是评测插件太神了，还是数据太淼了？ _Itachi
2016-10-15 14:28
6楼
| ||||
|
我晕，第一次交WA一个点（第6个）是怎么回事？
结果发现是最短路写搓了。。 _Itachi
2016-10-15 13:48
5楼
| ||||
|
这题为什么看不了错误数据点的数据了
 wrz91win
2015-10-02 20:38
4楼
| ||||
|
是不是卡了，跪求大神解决
| ||||
|
回复 @Makazeu :
同跪+1 | ||||
|
跪求大神的講解！！
我檢查了幾遍代碼，結果還是3A4P3E。 | ||||
FoolMike
可以的.
NVIDIA
天一阁
Makazeu
可可和卡卡家住HF市的东郊，每天上学他们都要转车多次才能到达市区西端的学校。直到有一天他们两人参加了学校的信息学奥林匹克竞赛小组才发现每天上学的乘车路线不一定是最优的。
可可：“很可能我们在上学的路途上浪费了大量的时间，让我们写一个程序来计算上学需要的最少时间吧！”
HF市一共设有N个公交车站，不妨将它们编号为 1…N的自然数，并认为可可和卡卡家住在 1 号汽车站附近，而他们学校在N号汽车站。市内有M条直达汽车路线，执行第i条路线的公交车往返于站点pi 和qi 之间，从起点到终点需要花费的时间为t i。 (1<=i<=M, 1<=p i,q i<=N)
两个人坐在电脑前，根据上面的信息很快就编程算出了最优的乘车方案。然而可可忽然有了一个鬼点子，他想趁卡卡不备，在卡卡的输入数据中删去一些路线，从而让卡卡的程序得出的答案大于实际的最短时间。而对于每一条路线i事实上都有一个代价c i：删去路线的c i越大卡卡就越容易发现这个玩笑，可可想知道什么样的删除方案可以达到他的目的而让被删除的公交车路线c i之和最小。
[ 任务 ]
编写一个程序：
• 从输入文件中读取HF市公交路线的信息；
• 计算出实际上可可和卡卡上学需要花费的最少时间；
• 帮助可可设计一个方案，删除输入信息中的一些公交路线，使得删除后从家到学校需要的最少时间变大，而被删除路线的c i和最小；
• 向输出文件输出答案。
[ 输入格式 ]
输入文件中第一行有两个正整数N和M，分别表示HF市公交车站和公交汽车路线的个数。以下M行，每行（第i行，总第 (i+1) 行）用四个正整数描述第i条路线：p i,q i,t i,c i；具体含义见上文描述。
[ 输出格式 ]
输出文件最多有两行。
第一行中仅有一个整数，表示从可可和卡卡家到学校需要的最短时间。
第二行描述你为可可制定的方案，首先有两个整数K和C，表示总共需要删除K条路线，它们的c i之和为C最小；
接着有K行，每行1个 1…N的正整数：d1 ,d2 , …,d K，表示需要删除的路线编号，即输入文件中顺数的编号。如果有多解，输出任意一个。
[ 输入样例 ]
6 7
1 2 1 3
2 6 1 5
1 3 1 1
3 4 1 1
4 6 1 1
5 6 1 2
1 5 1 4
1 2 1 3
2 6 1 5
1 3 1 1
3 4 1 1
4 6 1 1
5 6 1 2
1 5 1 4
[ 输出样例 ]
2
2 5
2 5
1
6
[ 数据约束 ]
2<=N<=500, 1<=M<=124 750, 1<=t i,c i<=10 000（评测插件有些问题，如果评测结果有误，请下载数据手动评测——Mike）
HF市的公交网络十分发达，你可以认为任意两个车站间都可以通过直达或转车互相到达，当然如果在你提供的删除方案中，家和学校无法互相到达，那么则认为上学需要的最短为正无穷大：这显然是一个合法的方案。