编程介的小学生 2019-12-28 19:58 采纳率: 20.5%
浏览 95

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

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
    • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
    • ¥15 Arcgis相交分析无法绘制一个或多个图形
    • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
    • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
    • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
    • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
    • ¥30 3天&7天&&15天&销量如何统计同一行
    • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
    • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型