原文地址：http://www.cnblogs.com/GXZlegend/p/6832504.html
题目描述
皮卡丘被火箭队用邪恶的计谋抢走了！这三个坏家伙还给小智留下了赤果果的挑衅！为了皮卡丘，也为了正义，小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。
火箭队一共有N个据点，据点之间存在M条双向道路。据点分别从1到N标号。小智一行K人从真新镇出发，营救被困在N号据点的皮卡丘。为了方便起见，我们将真新镇视为0号据点，一开始K个人都在0号点。
由于火箭队的重重布防，要想摧毁K号据点，必须按照顺序先摧毁1到K-1号据点，并且，如果K-1号据点没有被摧毁，由于防御的连锁性，小智一行任何一个人进入据点K，都会被发现，并产生严重后果。因此，在K-1号据点被摧毁之前，任何人是不能够经过K号据点的。
为了简化问题，我们忽略战斗环节，小智一行任何一个人经过K号据点即认为K号据点被摧毁。被摧毁的据点依然是可以被经过的。
K个人是可以分头行动的，只要有任何一个人在K-1号据点被摧毁之后，经过K号据点，K号据点就被摧毁了。显然的，只要N号据点被摧毁，皮卡丘就得救了。
野外的道路是不安全的，因此小智一行希望在摧毁N号据点救出皮卡丘的同时，使得K个人所经过的道路的长度总和最少。
请你帮助小智设计一个最佳的营救方案吧！
输入
第一行包含三个正整数N，M，K。表示一共有N+1个据点，分别从0到N编号，以及M条无向边。一开始小智一行共K个人均位于0号点。
接下来M行，每行三个非负整数，第i行的整数为Ai，Bi，Li。表示存在一条从Ai号据点到Bi号据点的长度为Li的道路。
输出
仅包含一个整数S，为营救皮卡丘所需要经过的最小的道路总和。
样例输入
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。
因为必须在编号小的点都被摧毁的条件下才能算编号大的点的路径。
这样就求出了题目条件下的两点最短路。
然后就转化为类似于 的问题，拆点费用流即可。
#include#include #include #define inf 0x3f3f3f3fusing namespace std;queue 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;}