题目描述

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

题目分析

一眼最小割 但是我们的最小割只能割边
不怕 我们进行拆点：A-> A' B->B' 为了使得经过这个点都会经过我们拆边的边权 所以我们：A'->B B'->A

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int inf=0x3f3f3f3f;
int n,m,tot=1;
int head[3000],to[100010],net[100010],val[100010],value[3000];
int a,b;
void add(int x,int y,int c)
{
    net[++tot]=head[x],head[x]=tot,to[tot]=y,val[tot]=c;
    net[++tot]=head[y],head[y]=tot,to[tot]=x,val[tot]=0;
}
int ans,s,t;
int dis[3000];
int bfs()
{
    queue<int>q;
    while(!q.empty())q.pop();
    memset(dis,0,sizeof dis);
    q.push(s);
    dis[s]=1;
    while(q.size())
    {
        int nmp=q.front();
        q.pop();
        for(int i=head[nmp];i;i=net[i])
            if(val[i]>0&&!dis[to[i]])
            {
                dis[to[i]]=dis[nmp]+1;
                q.push(to[i]);
                if(to[i]==t) return 1;
            }
    }
    return 0;
}
int dinic(int x,int flow)
{
    int tmp,temp=flow;
    if(x==t) return flow;
    for(int i=head[x];i;i=net[i])
        if(val[i]>0&&dis[to[i]]==dis[x]+1)
        {
            tmp=dinic(to[i],min(val[i],temp));
            if(tmp==0) dis[to[i]]=0;
            temp-=tmp,val[i]-=tmp,val[i^1]+=tmp;
            if(!temp) break;
        }
    return flow-temp;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&a,&b);
    for(int i=1;i<=n;i++) scanf("%d",&value[i]),add(i,i+n,value[i]);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(y+n,x,inf),add(x+n,y,inf);
    }
    s=a,t=b+n;
    while(bfs()) ans+=dinic(s,1<<30);
    printf("%d",ans);
    return 0;
}