[BZOJ1163][BZOJ1339][Baltic2008]Mafia
试题描述
匪徒准备从一个车站转移毒品到另一个车站,警方准备进行布控. 对于每个车站进行布控都需要一定的代价,现在警方希望使用最小的代价控制一些车站,使得去掉这些车站后，匪徒无法从原定的初始点到达目标点
输入
第一行输入N,M代表车站的总个数,及有多少条双向边连接它们. 2<=n<=200 , 1 <=m<=20000. 第二行给出两个数a,b,代表匪徒的出发点及目标点.1<=a,b<=N,a<>b. 再下来有N行,给出对第i个车站进行布控所需要的Money,其不超过10 000 000 再下来M行,用于描述图的结构.
输出
最少需要多少Money
输入示例
输出示例
数据规模及约定
见“输入”
题解
一个点拆成一个“入点”A 和“出点”B，A → B 连一条容量为权值的有向边，无向边拆分成两个有向边，跑一边最小割。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std; const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *tail;
inline char Getchar() {
if(Head == tail) {
int l = fread(buffer, 1, BufferSize, stdin);
tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
} #define maxn 410
#define maxm 80410
#define oo 2147483647
struct Edge { int from, to, flow; } ;
struct Dinic {
int n, m, s, t, head[maxn], next[maxm];
Edge es[maxm];
int vis[maxn], Q[maxn], hd, tl;
int cur[maxn];
void init(int nn) {
n = nn; m = 0;
memset(head, -1, sizeof(head));
return ;
}
void AddEdge(int a, int b, int c) {
es[m] = (Edge){ a, b, c }; next[m] = head[a]; head[a] = m++;
es[m] = (Edge){ b, a, 0 }; next[m] = head[b]; head[b] = m++;
return ;
}
bool BFS() {
memset(vis, 0, sizeof(vis));
vis[s] = 1;
hd = tl = 0; Q[++tl] = s;
while(hd < tl) {
int u = Q[++hd];
for(int i = head[u]; i != -1; i = next[i]) {
Edge& e = es[i];
if(e.flow && !vis[e.to]) {
vis[e.to] = vis[u] + 1;
Q[++tl] = e.to;
}
}
}
return vis[t] > 0;
}
int DFS(int u, int a) {
if(u == t || !a) return a;
int flow = 0, f;
for(int& i = cur[u]; i != -1; i = next[i]) {
Edge& e = es[i];
if(vis[e.to] == vis[u] + 1 && (f = DFS(e.to, min(a, e.flow)))) {
flow += f; a -= f;
e.flow -= f; es[i^1].flow += f;
if(!a) return flow;
}
}
return flow;
}
int MinCut(int ss, int tt) {
s = ss; t = tt;
int flow = 0;
while(BFS()) {
for(int i = 1; i <= n; i++) cur[i] = head[i];
flow += DFS(s, oo);
}
return flow;
}
} sol; int main() {
int n = read(), m = read();
sol.init(n << 1);
int s = (read() << 1) - 1, t = read() << 1;
for(int i = 1; i <= n; i++) sol.AddEdge((i << 1) - 1, i << 1, read());
for(int i = 1; i <= m; i++) {
int u = read(), v = read();
sol.AddEdge(u << 1, (v << 1) - 1, oo);
sol.AddEdge(v << 1, (u << 1) - 1, oo);
} printf("%d\n", sol.MinCut(s, t)); return 0;
}