网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
战争传说
成绩 | 开启时间 | 2014年09月19日 星期五 10:07 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:07 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:07 |
输入文件 | war.in | 输出文件 | war.out |
【题目描述】
在遥远的地方有一个大海。
在大海上有N个小岛。
有一些有向的桥将这些小岛连接起来。
有一个叫做“壹号国”的国家位于1号小岛上。
还有一个叫做“其它国”的国家位于N号小岛上。
“壹号国”起兵进攻“其它国”,挑起了一场战争。
“其它国”想到了一个策略,想通过破坏一些桥,斩断1号小岛同N号小岛的联系,借此来实现防守。
破坏不同的桥有不同的代价。
“其它国”有个大仙儿,能掐会算,他能算出来为实现防守策略而拆桥所需要的最小代价。
“壹号国”有一个建筑队,能把一个桥重建并使其坚不可摧,他们也能在2~N-1号小岛任意两个小岛间新建一个坚不可摧的桥。
但是在“其它国”开始拆桥之前,“壹号国”没有足够的时间了,所以它只能新建一个桥或者将一个已经存在的桥重建。
现在问题是:“壹号国”想让“其它国”拆桥的最小代价最大化,那么那个可能的最大解是多少呢?
【输入格式】
输入文件有多组测试数据。
文件的第一行有一个整数,即接下来测试数据的个数,不超过100组。
对于每个测试数据,第一行有两个数:N,M,(4<=N<=100;
0<=M<=N*(N-1)/2),分别表示小岛的个数及桥的个数。
接下来有M行,每一行有三个整数a,b,c,(1<=a,b<=N;
1<=c<=10000),表示有一个有向的桥从小岛a连向小岛b,拆除它的代价为c。
数据保证没有重边。
【输出格式】
对于每个测试数据,输出只有一行,即上述可能的最大解。
【样例输入】
4 4 0 4 2 1 2 2 3 4 2 4 3 1 2 1 2 3 1 3 4 10 4 3 1 2 5 2 3 2 3 4 3
【样例输出】
0 2 1 3
【提示】
在此键入。
【来源】
在此键入。