[BZOJ1585][Usaco2009 Mar]Earthquake Damage 2 地震伤害 最小割



给出一个图,告诉一些点和1号点不连通,求最少删掉几个点.
很显然的最小割模型,将每个点拆点,中间的边是inf(给出的点或1号点)或1(其他点),原图中的边保留,容量是inf;新建汇点,连向每个给出的点,容量是inf.从1号点到汇点跑一下最小割.

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 23333
#define M 233333
using namespace std;
int head[N],to[M],next[M],f[M],tot=1;
const int inf=999999999;
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,p;
int dis[N];
queue<int>q;
bool bfs()
{
    while(!q.empty())q.pop();
    memset(dis,-1,sizeof dis);
    q.push(s);dis[s]=0;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=head[x];i;i=next[i])if(f[i]&&dis[to[i]]==-1)
        {
            dis[to[i]]=dis[x]+1;
            if(to[i]==t)return 1;
            q.push(to[i]);
        }
    }
    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(f[i],temp));
        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(1,999999999);
    return re;
}
int main()
{
    cin>>n>>m>>p;
    s=1,t=n*2+1;
    for(int x,y,i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add(n+x,y,inf);
        add(n+y,x,inf);
    }
    for(int x,i=1;i<=p;i++)
    {
        scanf("%d",&x);
        add(x+n,t,inf);
    }
    for(int i=1;i<=n;i++)
    {
        if(to[head[i+n]]==t||i==1)add(i,i+n,inf);
        else add(i,i+n,1);
    }
    printf("%d\n",maxflow());
    return 0;
}

发表评论

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