题解-P2944

本文章遵守知识共享协议 CC-BY-NC-SA，同步发表于洛谷题解区，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

题面大意

在一个无向图中，总共有 $P$ 个点，$C$ 条边。

其中一些点被摧毁了，不过可以确定的是至少 $N(1 \le N \le P)$ 个点没有被摧毁，但是与 $1$ 号点没有连边，请确定可能被摧毁的点的最少数量。

解题思路

看到摧毁和多点连通性，我想到了网络流，但是第一个想到的不是网络流而是其它的算法，不过碍于篇幅和正确性，这里就不放出来了。

我们发现，这里的边是不会被摧毁的，只有代表牧场的点可能被摧毁。所以我们先拆点，将每个点套路化地拆成入点和出点，并根据题目信息建图。

而点中间的流量呢？很简单，确定没有被摧毁的点是不能被割掉的，但是它不能到达 $1$ 号点，所以中间是有点要被割掉的，要将源点与其连一条不可割的边，在入点和出点之间连一条不可割的边。

而对于状态不确定的点，都是有可能被割掉的，所以我们要在源点与其连一条不可割的边，在入点和出点之间连一条割代价为 $1$ 的边。

至于汇点，编号显然是 $1$。因为你讨论的是每个点与牛棚的可达性。

核心代码如下：

int cut[N];

signed main() {
	scanf("%lld%lld%lld",&n,&m,&k);
	s = 2*n+1;
	while(m--)
		scanf("%lld%lld",&u,&v),
		add(u+n,v,inf),
		add(v+n,u,inf);
	for(int i=1; i<=k; i++)
		scanf("%lld",&tp),
		cut[tp]=1;
	for(int i=1; i<=n; i++)
		if(cut[i])
			add(s,i,inf),
			add(i,i+n,inf);
		else
			add(i,i+n,1);
	t=1;
	printf("%lld",dinic());
	return 0;
}