原文地址：http://www.cnblogs.com/GXZlegend/p/6832504.html

---

題目描述

皮卡丘被火箭隊用邪惡的計謀搶走了！這三個壞家伙還給小智留下了赤果果的挑釁！為了皮卡丘，也為了正義，小智和他的朋友們義不容辭的踏上了營救皮卡丘的道路。

火箭隊一共有N個據(jù)點，據(jù)點之間存在M條雙向道路。據(jù)點分別從1到N標號。小智一行K人從真新鎮(zhèn)出發(fā)，營救被困在N號據(jù)點的皮卡丘。為了方便起見，我們將真新鎮(zhèn)視為0號據(jù)點，一開始K個人都在0號點。

由于火箭隊的重重布防，要想摧毀K號據(jù)點，必須按照順序先摧毀1到K-1號據(jù)點，并且，如果K-1號據(jù)點沒有被摧毀，由于防御的連鎖性，小智一行任何一個人進入據(jù)點K，都會被發(fā)現(xiàn)，并產(chǎn)生嚴重后果。因此，在K-1號據(jù)點被摧毀之前，任何人是不能夠經(jīng)過K號據(jù)點的。

為了簡化問題，我們忽略戰(zhàn)斗環(huán)節(jié)，小智一行任何一個人經(jīng)過K號據(jù)點即認為K號據(jù)點被摧毀。被摧毀的據(jù)點依然是可以被經(jīng)過的。

K個人是可以分頭行動的，只要有任何一個人在K-1號據(jù)點被摧毀之后，經(jīng)過K號據(jù)點，K號據(jù)點就被摧毀了。顯然的，只要N號據(jù)點被摧毀，皮卡丘就得救了。

野外的道路是不安全的，因此小智一行希望在摧毀N號據(jù)點救出皮卡丘的同時，使得K個人所經(jīng)過的道路的長度總和最少。

請你幫助小智設計一個最佳的營救方案吧！

輸入

第一行包含三個正整數(shù)N，M，K。表示一共有N+1個據(jù)點，分別從0到N編號，以及M條無向邊。一開始小智一行共K個人均位于0號點。?

接下來M行，每行三個非負整數(shù)，第i行的整數(shù)為Ai，Bi，Li。表示存在一條從Ai號據(jù)點到Bi號據(jù)點的長度為Li的道路。

輸出

僅包含一個整數(shù)S，為營救皮卡丘所需要經(jīng)過的最小的道路總和。

樣例輸入

3 4 2
0 1 1
1 2 1
2 3 100
0 3 1

樣例輸出

3

---

題解

最短路-Floyd+有上下界費用流

先用Floyd求出任意兩點間距離，注意這里的路徑是帶有條件的，若為i與j之間的距離，則中間枚舉點k必須滿足k<=i或k<=j。

因為必須在編號小的點都被摧毀的條件下才能算編號大的點的路徑。

這樣就求出了題目條件下的兩點最短路。

然后就轉(zhuǎn)化為類似于 bzoj1927 的問題，拆點費用流即可。

#include <cstdio> #include <cstring> #include <queue> #define inf 0x3f3f3f3f using namespace std; queue<int> q; int map[160][160] , head[400] , to[100000] , val[100000] , cost[100000] , next[100000] , cnt = 1 , s , t , dis[400] , from[400] , pre[400]; void add(int x , int y , int v , int c) {to[++cnt] = y , val[cnt] = v , cost[cnt] = c , next[cnt] = head[x] , head[x] = cnt;to[++cnt] = x , val[cnt] = 0 , cost[cnt] = -c , next[cnt] = head[y] , head[y] = cnt; } bool spfa() {int x , i;memset(dis , 0x3f , sizeof(dis));memset(from , -1 , sizeof(from));dis[s] = 0 , q.push(s);while(!q.empty()){x = q.front() , q.pop();for(i = head[x] ; i ; i = next[i])if(val[i] && dis[to[i]] > dis[x] + cost[i])dis[to[i]] = dis[x] + cost[i] , from[to[i]] = x , pre[to[i]] = i , q.push(to[i]);}return ~from[t]; } int mincost() {int ans = 0 , i , k;while(spfa()){k = inf;for(i = t ; i != s ; i = from[i]) k = min(k , val[pre[i]]);ans += dis[t] * k;for(i = t ; i != s ; i = from[i]) val[pre[i]] -= k , val[pre[i] ^ 1] += k;}return ans; } int main() {int n , m , p , i , j , k , x , y , z;scanf("%d%d%d" , &n , &m , &p);memset(map , 0x3f , sizeof(map));while(m -- ) scanf("%d%d%d" , &x , &y , &z) , map[x][y] = map[y][x] = min(map[x][y] , z);for(k = 0 ; k <= n ; k ++ )for(i = 0 ; i <= n ; i ++ )for(j = 0 ; j <= n ; j ++ )if((k <= i || k <= j) && map[i][j] > map[i][k] + map[k][j])map[i][j] = map[i][k] + map[k][j];s = 2 * n + 2 , t = 2 * n + 3 , add(2 * n + 1 , 0 , p , 0);for(i = 1 ; i <= n ; i ++ ) add(0 , i , inf , map[0][i]);for(i = 1 ; i <= n ; i ++ ){add(s , i + n , 1 , 0) , add(i , t , 1 , 0) , add(i + n , 2 * n + 1 , inf , 0);for(j = i + 1 ; j <= n ; j ++ )if(map[i][j] != inf)add(i + n , j , inf , map[i][j]);}printf("%d\n" , mincost());return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/GXZlegend/p/6832504.html

總結(jié)

以上是生活随笔為你收集整理的【bzoj2324】[ZJOI2011]营救皮卡丘 最短路-Floyd+有上下界费用流的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。