There is a war (hdu 2435 最小割+枚舉)
There is a war
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 970 Accepted Submission(s): 277
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
Source 2008 Asia Chengdu Regional Contest Online
Recommend lcy | We have carefully selected several similar problems for you: 2433 2432 2430 2429 2431
題意:n個國家,m條有向邊,國家1要去攻打國家n,n想切斷1到n的道路來防御,切斷每條道路有一定費用,國家1有一個NB魔法,可以建一條新邊或者加固一條已有的邊,這條邊不能被n破壞,現在求 最大化n國花費之和的最小值。
思路:可知就是求最小割邊集,先建圖,跑一遍最大流得ans,然後從S集到T集枚舉割邊使容量為INF,在殘留網絡中再跑網絡流並記錄最大值Max,那麼最後答案就是ans+Max。在枚舉的時候也可以直接重新建圖,這樣應該好理解一些。
代碼:
#include
#include
#include
#include
#include
#include
#include
#include