Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 1163: [Baltic2008]Mafia

题目链接

传送门

Description

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

Input

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

Output

最少需要多少Money

Sample Input

5 6

5 3

2

4

8

3

10

1 5

1 2

2 4

4 5

2 3

3 4

Sample Output

5

题解

直接拆点最小割
一个点的点权 看成i->i+n这条边上val[i]的流量
然后超级源点 超级汇点ok

代码

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏