【bzoj1163/bzoj1339】[Baltic2008]Mafia网络流最小割

题目描述

匪徒准备从一个车站转移毒品到另一个车站,警方准备进行布控. 对于每个车站进行布控都需要一定的代价,现在警方希望使用最小的代价控制一些车站,使得去掉这些车站后&＃xff0c;匪徒无法从原定的初始点到达目标点

输入

第一行输入N,M代表车站的总个数,及有多少条双向边连接它们. 2<&＃61;n<&＃61;200 , 1 <&＃61;m<&＃61;20000. 第二行给出两个数a,b,代表匪徒的出发点及目标点.1<&＃61;a,b<&＃61;N,a<>b. 再下来有N行,给出对第i个车站进行布控所需要的Money,其不超过10 000 000 再下来M行,用于描述图的结构.

输出

最少需要多少Money

样例输入

5 6
5 3
2
4
8
3
10
1 5
1 2
2 4
4 5
2 3
3 4

样例输出

5

题解

网络流最小割

每个点拆成两个&＃xff0c;设为x[i]和y[i]&＃xff0c;连边x[i]->y[i]&＃xff0c;容量为布控需要的Money。

对于原图中的边i<->j&＃xff0c;连边y[i]->x[j]和y[j]->x[i]&＃xff0c;容量均为inf。

然后以x[a]为源点&＃xff0c;y[b]为汇点求最小割即为答案。