[文章目录]
Description
给出一张n个点，m条边的无向图，并给出一些已经选的点。求出最小不包含这些点的点集，使得所选的点不经过点集中的任意一个点不能到达1节点。n<=3000 m<=20000
网络流最小割。
拆点，将所有点中不能选的流量都为inf，其余都为1.然后s连向这些点，原图保留，边的流量为inf，最小割即为答案。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,p,s,t,ans;
int head[6100],to[101000],nxt[101000],f[101000],cnt=1;
bool v[3100];
void add(int x,int y,int z)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
f[cnt]=z;
}
queue<int>q;
int dis[6100];
bool bfs()
{
while(!q.empty()) q.pop();
memset(dis,-1,sizeof(dis));
dis[s]=0; q.push(s);
int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]<0)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int tmp=flow,xx;
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) break;
}
return flow-tmp;
}
int main()
{
scanf("%d%d%d",&n,&m,&p);
int x,y; s=2*n+1; t=1;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x+n,y,inf);
add(y,x+n,0);
add(y+n,x,inf);
add(x,y+n,0);
}
for(int i=1;i<=p;i++)
{
scanf("%d",&x); v[x]=1;
}
for(int i=1;i<=n;i++)
{
if(v[i])
{
add(i,i+n,inf);
add(i+n,i,0);
add(s,i,inf);
add(i,s,0);
}
else
{
add(i,i+n,1);
add(i+n,i,0);
}
}
while(bfs()) ans+=dinic(s,inf);
printf("%d\n",ans);
return 0;
}