題目鏈接：POJ 2391 Ombrophobic Bovines
|
Ombrophobic Bovines
Description
FJ's cows really hate getting wet so much that the mere thought of getting caught in the rain makes them shake in their hooves. They have decided to put a rain siren on the farm to let them know when rain is approaching. They intend to create a rain evacuation
plan so that all the cows can get to shelter before the rain begins. Weather forecasting is not always correct, though. In order to minimize false alarms, they want to sound the siren as late as possible while still giving enough time for all the cows to get
to some shelter.
The farm has F (1 <= F <= 200) fields on which the cows graze. A set of P (1 <= P <= 1500) paths connects them. The paths are wide, so that any number of cows can traverse a path in either direction. Some of the farm's fields have rain shelters under which the cows can shield themselves. These shelters are of limited size, so a single shelter might not be able to hold all the cows. Fields are small compared to the paths and require no time for cows to traverse. Compute the minimum amount of time before rain starts that the siren must be sounded so that every cow can get to some shelter. Input
* Line 1: Two space-separated integers: F and P
* Lines 2..F+1: Two space-separated integers that describe a field. The first integer (range: 0..1000) is the number of cows in that field. The second integer (range: 0..1000) is the number of cows the shelter in that field can hold. Line i+1 describes field i. * Lines F+2..F+P+1: Three space-separated integers that describe a path. The first and second integers (both range 1..F) tell the fields connected by the path. The third integer (range: 1..1,000,000,000) is how long any cow takes to traverse it. Output
* Line 1: The minimum amount of time required for all cows to get under a shelter, presuming they plan their routes optimally. If it not possible for the all the cows to get under a shelter, output "-1".
Sample Input 3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120
Sample Output 110
Hint
OUTPUT DETAILS:
In 110 time units, two cows from field 1 can get under the shelter in that field, four cows from field 1 can get under the shelter in field 2, and one cow can get to field 3 and join the cows from that field under the shelter in field 3. Although there are other plans that will get all the cows under a shelter, none will do it in fewer than 110 time units. Source
USACO 2005 March Gold
|
題意：
農場有F塊草地，奶牛們在草地上吃草。這些草地之間有P條路相連，路足夠寬，可以同時通過無限頭奶牛。有些草地有避雨點，奶牛們可以在此避雨。避雨點容量有限，一個避雨點不能容納所有奶牛。草地與路相比很小，奶牛通過草地時不需要時間。求所有奶牛都回到避雨點所花的最小時間。如果不能保證都能到避雨點，則輸出-1。
分析：
這道題和POJ 2112挺像。不過要難一些。
首先需要用Floyd算出所有點之間的最短距離。然后二分枚舉距離求最大流，求到的滿足最大流等于牛頭數的那個最小的距離即為答案。
但是出現了一個問題，結點現在也有了容量，因而我們需要拆點，把一個原始結點u分裂成u1和u2兩個結點，中間連一條有向弧，容量等于結點容量。原先到達u的弧改成到達u1，原先從u出發的弧改成u2出發。
構圖：
找一個源點s，一個匯點t，s和每個草地連一條邊，容量為草地上的牛數，每個避雨點和t連一條邊，容量為避雨點容納牛頭數。
拆點問題如上所述。
如果一塊草地到另一塊草地有最短路，且這個最短路小于當前枚舉到的路徑長度，那么這兩塊草地連一條邊，容量為無窮，因為可以走無限頭。
求解枚舉滿足最小值。
代碼：
寫了好多遍都T了，最后把vector和queue都換成了普通數組，然后過了，只給了1秒，實在太坑了。
T了好多次，把STL刪掉越來越好，也是醉了：
| Run ID | User | Problem | Result | Memory | Time | Language | Code Length | Submit Time |
| 13481032 | acmer | 2391 | Accepted | 5112K | 610MS | G++ | 3159B | 2014-09-26 22:37:24 |
| 13480087 | acmer | 2391 | Accepted | 5112K | 625MS | G++ | 3203B | 2014-09-26 17:43:11 |
| 13480059 | acmer | 2391 | Accepted | 5136K | 641MS | G++ | 3215B | 2014-09-26 17:33:17 |
| 13480007 | acmer | 2391 | Accepted | 5240K | 704MS | G++ | 3199B | 2014-09-26 17:20:58 |
| 13479803 | acmer | 2391 | Accepted | 3344K | 922MS | G++ | 2349B | 2014-09-26 16:39:45 |
上一篇 Linux中的hostname
下一篇 beego開發環境
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
