题目描述

Wisconsin has had an earthquake that has struck Farmer John's farm! The earthquake has damaged some of the pastures so that they are unpassable. Remarkably, none of the cowpaths was damaged.
As usual, the farm is modeled as a set of P () pastures conveniently numbered 1..P which are connected by a set of C () non-directional cowpaths conveniently numbered 1..C. Cowpath i connects pastures and  (). Cowpaths might connect   to itself or perhaps might connect two pastures more than once. The barn is located in pasture 1.
A total of N () cows (in different pastures) sequentially contact Farmer John via mobile phone with an integer message () that indicates that pasture  is undamaged but that the alling cow is unable to return to the barn from pasture  because she could not find a ath that does not go through damaged pastures.
After all the cows report in, determine the minimum number of pastures that are damaged.

输入描述:

* Line 1: Three space-separated integers: P, C, and N
* Lines 2..C+1: Line i+1 describes cowpath i with two integers:  and 
* Lines C+2..C+N+1: Line C+1+j contains a single integer: 

输出描述:

* Line 1: A single integer that is the minimum count of pastures from which a cow can not return to the barn (including the damaged pastures themselves)

示例1

输入
5 5 2
1 2
2 3
3 5
2 4
4 5
4
5
输出
1

说明

Only pasture 2 being damaged gives such a scenario.

解答

问题转化：已确定几个点不割，问最少割几个点使图分成两部分

于是考虑最小割

建图，因为最小割是割边，所以拆点

即把每个点拆为入点和出点

确定的点，入点出点之间连边为∞∞

保证最小割集合中不包含这个点，并且与超汇点连边为∞∞

保证经过确定点

未确定点，入点出点之间连边为11

最小割集合中可以包含这个点

注意是双向边，还有11点也是确定点

代码： 

# include<iostream>
# include<cstdio>
# include<cstring>
# include<queue>
using namespace std;
const int t=500000;
struct q{
    int x,y,dis;
}c[6000001];
int p,C,n,num;
int h[600001],d[600001];
bool use[3001];
void add(int x,int y,int dis)
{
    c[num].x=h[x];
    c[num].y=y;
    c[num].dis=dis;
    h[x]=num++;
}
bool bfs()
{
    queue<int> qu;
    qu.push(0);
    memset(d,0,sizeof(d));
    d[0]=1;
    while(!qu.empty())
    {
        int tt=qu.front();
        qu.pop();
        for(int i=h[tt];i;i=c[i].x)
          if(!d[c[i].y]&&c[i].dis)
          {
              d[c[i].y]=d[tt]+1;
              qu.push(c[i].y);
          }
    }
    return d[t];
}
int dfs(int x,int dix)
{
    if(x==t) return dix;
    int sum=0;
    for(int i=h[x];i;i=c[i].x)
      if(d[c[i].y]==d[x]+1&&c[i].dis)
      {
          int dis=dfs(c[i].y,min(dix,c[i].dis));
          if(dis)
          {
              sum+=dis;
              dix-=dis;
              c[i].dis-=dis;
              c[i^1].dis+=dis;
              if(!dix) break;
        }
      }
    return sum;
}
int dinic()
{
    int tot=0;
    while(bfs())
    tot+=dfs(0,1e8);
    return tot;
}
int main()
{
    scanf("%d%d%d",&p,&C,&n);
    add(1,0,0);
    add(0,1,1e8);
    add(1+p,1,0);
    add(1,1+p,1e8);
    for(int i=1;i<=C;i++)
      {
          int x,y;
          scanf("%d%d",&x,&y);
          add(x,y+p,0);
          add(y+p,x,1e8);
          add(y,x+p,0);
          add(x+p,y,1e8);
      }
    for(int i=1;i<=n;i++)
      {
          int x;
          scanf("%d",&x);
          use[x]=1; 
          add(x+p,x,0);
          add(x,x+p,1e8);
        add(t,x+p,0);
          add(x+p,t,1e8);
      }
    for(int i=2;i<=p;i++)
      if(!use[i])
      {
          add(i+p,i,0);
          add(i,i+p,1);
      }
    printf("%d",dinic());
    return 0;
}


来源：Dispwnl