bzoj 1585: [Usaco2009 Mar]Earthquake Damage 2 地震伤害

1585: [Usaco2009 Mar]Earthquake Damage 2 地震伤害

Description

Farmer John的农场里有P个牧场，有C条无向道路连接着他们，第i条道路连接着两个牧场Ai和Bi，注意可能有很多条道路连接着相同的Ai和Bi，并且Ai有可能和Bi相等。Farmer John在1号牧场里。由于地震，某些牧场被损坏，但由于信春哥，C条道路没有一条损坏。有N头奶牛，他们在不同的牧场里，于是N <= P。他们一一向Farmer John报告。第i头奶牛报告给Farmer John一个整数Report_i，代表第Report_i个牧场没有损毁，但不能够从第Report_i个牧场经过一些没有损坏的牧场到达1号牧场。现在Farmer John想知道，最少有多少损坏的牧场。

Input

第一行三个整数 P，C，N

第2..C+1行：每行两个整数Ai,Bi

第C+2..C+N+1行：第C+1+i行包含一个整数，Report_i

Output

一个整数，代表最少有多少损坏的牧场

Sample Input

5 5 2
1 2
2 3
3 5
2 4
4 5
4
5

Sample Output

1
【数据规模】
1 <= P <=3000
1 <= C <=20000

题解：

拆点，最小割。。。

由于1到不了给定的一些点，那么就是求图中的割，将给定的点向T连一条边权无穷大的边，保证割使1和这些点分离。。

题目中还说给定的点没有毁坏，以此将一个点x裂成x,x’

若是1或是给定的点,x->x’  ∞

反之x->x’  1

对于相邻的<x,y>

x’->y  ∞

y’->x  ∞

#include<stdio.h>
#include<iostream>
using namespace std;
const int N=6005;
const int M=100005;
int n,m,k,i,x,y,src,tar,ans,dis[N],gap[N],p[N];
int tot,head[N],Next[M],to[M],v[M];
void add(int x,int y,int z)
{
    to[tot]=y;
    v[tot]=z;
    Next[tot]=head[x];
    head[x]=tot++;
}
inline void read(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
int isap(int x,int s)
{
    if(x==tar) return s;
    int flow=0,i,Min=n-1;
    for(i=head[x];i!=-1;i=Next[i])
    {
        int y=to[i];
        if(v[i]>0)
        {
            if(dis[x]==dis[y]+1)
            {
                int tmp=isap(y,min(s-flow,v[i]));
                flow+=tmp;
                v[i]-=tmp;
                v[i^1]+=tmp;
            }
            Min=min(Min,dis[y]);
        }
        if(flow==s) return flow;
        if(dis[src]==n) return flow;
    }
    if(flow==0)
    {
        gap[dis[x]]--;
        if(gap[dis[x]]==0) dis[src]=n;
        dis[x]=Min+1;
        gap[dis[x]]++;
    }
    return flow;
}
int main()
{
    read(n),read(m),read(k);
    for(i=1;i<=n*2+2;i++) head[i]=-1;
    src=n*2+1,tar=n*2+2;
    add(src,1,1e9);add(1,src,0);
    for(i=1;i<=m;i++)
    {
        read(x),read(y);
        add(x+n,y,1e9);add(y,x+n,0);
        add(y+n,x,1e9);add(x,y+n,0);
    }
    for(i=1;i<=k;i++)
    {
        read(x);
        add(x+n,tar,1e9);
        add(tar,x+n,0);
        p[x]=1;
    }
    for(i=1;i<=n;i++)
    {
        if(i==1||p[i])
        {
            add(i,i+n,1e9);
            add(n+i,i,0);
        } else
        {
            add(i,n+i,1);
            add(n+i,i,0);
        }
    }
    n=n*2+2;
    gap[0]=n;
    while(dis[src]<n)
        ans+=isap(src,1e9);
    cout<<ans;
    return 0;
}