Description
匪徒准备从一个车站转移毒品到另一个车站,警方准备进行布控. 对于每个车站进行布控都需要一定的代价,
现在警方希望使用最小的代价控制一些车站,使得去掉这些车站后，匪徒无法从原定的初始点到达目标点
Input
第一行输入N,M代表车站的总个数,及有多少条双向边连接它们
第二行给出两个数a,b,代表匪徒的出发点及目标点.1<=a,b<=N,a<>b.
再下来有N行,给出对第i个车站进行布控所需要的Money,其不超过10 000 000
再下来M行,用于描述图的结构.
2<=n<=200 , 1 <=m<=20000
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
Solution
直接拆点跑最小割就好了。
在(luogu)还要输出最小割的一种方案，那么可以从(s)开始(bfs)，沿着没流满的路径走，顺便走到的点标上(visited)，若一条边起点被访问过，终点没有，那么这条边就被割掉了，具体可以考虑下为什么最大流等于最小割。
这里附上求方案的版本。
#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}
const int maxn = 2e5+10;
const int inf = 1e9;
int n,m,s,t,tot=1;
int head[maxn],dis[maxn];
struct edge{int to,nxt,w;}e[maxn<<1];
void add(int u,int v,int w) {e[++tot]=(edge){v,head[u],w},head[u]=tot;}
void ins(int u,int v,int w) {add(u,v,w),add(v,u,0);}
int bfs() {
memset(dis,-1,sizeof dis);
queue<int > q;q.push(s);dis[s]=0;
while(!q.empty()) {
int x=q.front();q.pop();
for(int i=head[x];i;i=e[i].nxt)
if(e[i].w>0&&dis[e[i].to]==-1) {
dis[e[i].to]=dis[x]+1;
if(e[i].to==t) return 1;
q.push(e[i].to);
}
}
return 0;
}
int dfs(int x,int f) {
if(x==t) return f;
int used=0;
for(int i=head[x];i;i=e[i].nxt)
if(e[i].w>0&&dis[e[i].to]==dis[x]+1) {
int d=dfs(e[i].to,min(f-used,e[i].w));
if(d>0) e[i].w-=d,e[i^1].w+=d,used+=d;
if(used==f) break;
}
dis[x]=-1;return used;
}
int max_flow() {
int flow=0;
for(;bfs();flow+=dfs(s,inf));
return flow;
}
int vis[maxn];
void solve() {
queue<int > q;q.push(s);vis[s]=1;
while(!q.empty()) {
int x=q.front();q.pop();//write(x);
for(int i=head[x];i;i=e[i].nxt)
if(e[i].w>0&&!vis[e[i].to]) q.push(e[i].to),vis[e[i].to]=1;
}
for(int i=2;i<=tot;i+=2) if(vis[e[i^1].to]&&!vis[e[i].to]) printf("%d ",e[i^1].to);puts("");
}
int main() {
read(n),read(m),read(s),read(t);t+=n;
for(int i=1,x;i<=n;i++) read(x),ins(i,i+n,x);
for(int i=1,x,y;i<=m;i++) read(x),read(y),ins(x+n,y,inf),ins(y+n,x,inf);
max_flow();solve();
return 0;
}