[BZOJ1163/1339][Baltic2008]Mafia 最小割


给定起点和终点,每个点有花费,求最小代价删去一些点使得起点和终点不连通.
拆点最小割.

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 2333
#define M 233333
using namespace std;
const int inf=999999999;
int head[N],to[M],next[M],f[M],tot=1;
inline void add(int x,int y,int z)
{
    to[++tot]=y;f[tot]=z;next[tot]=head[x];head[x]=tot;
    to[++tot]=x;f[tot]=0;next[tot]=head[y];head[y]=tot;
}
int n,m,s,t,a,b;
int dis[N];
queue<int>q;
bool bfs()
{
    memset(dis,-1,sizeof dis);
    while(!q.empty())q.pop();
    q.push(s);dis[s]=0;
    int x,y;
    while(!q.empty())
    {
        x=q.front();q.pop();
        for(int i=head[x];i;i=next[i])if(dis[y=to[i]]==-1&&f[i])
        {
            dis[y]=dis[x]+1;
            if(y==t)return 1;
            q.push(y);
        }
    }
    return 0;
}
int dinic(int x,int flow)
{
    if(x==t)return flow;
    int a,temp=flow;
    for(int i=head[x];i;i=next[i])if(dis[to[i]]==dis[x]+1&&f[i])
    {
        a=dinic(to[i],min(temp,f[i]));
        if(!a)dis[to[i]]=-1;
        temp-=a,f[i]-=a,f[i^1]+=a;
        if(!temp)return flow;
    }
    return flow-temp;
}
int maxflow()
{
    int re=0;
    while(bfs())re+=dinic(s,inf);
    return re;
}
int main()
{
    cin>>n>>m>>a>>b;
    s=a,t=b+n;
    for(int z,i=1;i<=n;i++)
    {
        scanf("%d",&z);
        add(i,i+n,z);
    }
    for(int x,y,i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add(x+n,y,inf);
        add(y+n,x,inf);
    }
    cout<<maxflow();
    return 0;
}

发表评论

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