题目描述

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不能拆

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int tot=1,head[6010],to[100010],net[100010],val[100010];
int s,t;
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 dis[100010];
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 p;
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    s=1,t=2*n+1;
    add(1,n+1,1<<30);
    for(int i=2;i<=n;i++) add(i,i+n,1);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(y+n,x,1<<30),add(x+n,y,1<<30);
    }
    for(int i=1;i<=p;i++)
    {
        int x;
        scanf("%d",&x);
        add(x,x+n,1<<30),add(x+n,t,1<<30);
    }
    int ans=0;
    while(bfs())
        ans+=dinic(s,1<<30);
    printf("%d",ans);
    return 0;
}