编程介的小学生 2017-11-26 08:09 采纳率: 0.2%
浏览 864
已采纳

There is a war

Problem Description
There is a sea.
There are N islands in the sea.
There are some directional bridges connecting these islands.
There is a country called Country One located in Island 1.
There is another country called Country Another located in Island N.
There is a war against Country Another, which launched by Country One.
There is a strategy which can help Country Another to defend this war by destroying the bridges for the purpose of making Island 1 and Island n disconnected.
There are some different destroying costs of the bridges.
There is a prophet in Country Another who is clever enough to find the minimum total destroying costs to achieve the strategy.
There is an architecture in Country One who is capable enough to rebuild a bridge to make it unbeatable or build a new invincible directional bridge between any two countries from the subset of island 2 to island n-1.
There is not enough time for Country One, so it can only build one new bridge, or rebuild one existing bridge before the Country Another starts destroying, or do nothing if happy.
There is a problem: Country One wants to maximize the minimum total destroying costs Country Another needed to achieve the strategy by making the best choice. Then what’s the maximum possible result?

Input
There are multiple cases in this problem.
There is a line with an integer telling you the number of cases at the beginning.
The are two numbers in the first line of every case, N(4<=N<=100) and M(0<=M<=n*(n-1)/2), indicating the number of islands and the number of bridges.
There are M lines following, each one of which contains three integers a, b and c, with 1<=a, b<=N and 1<=c<=10000, meaning that there is a directional bridge from a to b with c being the destroying cost.
There are no two lines containing the same a and b.

Output
There is one line with one integer for each test case, telling the maximun possible result.

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

Sample Output
0
2
1
3

展开全部

  • 写回答

1条回答 默认 最新

  • threenewbee 2018-01-20 08:14
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
编辑
预览

报告相同问题?

悬赏问题

  • ¥15 fluent设置了自动保存后,会有几个时间点不保存
  • ¥20 激光照射到四象线探测器,通过液晶屏显示X、Y值
  • ¥15 这怎么做,怎么在我的思路下改下我这写的不对
  • ¥50 数据库开发问题求解答
  • ¥15 安装anaconda时报错
  • ¥20 如何用Python处理单元格内连续出现的重复词语?
  • ¥15 小程序有个导出到插件方式,我是在分包下引入的插件,这个export的路径对吗,我看官方文档上写的是相对路径
  • ¥20 希望有人能帮我完成这个设计( *ˊᵕˋ)
  • ¥100 将Intptr传入SetHdevmode()将Intptr传入后转换为DEVMODE的值与外部代码不一致
  • ¥50 基于ERA5数据计算VPD