自动搬运

查看原文

来自洛谷，原作者为

	zhy137036 AFO

搬运于2025-08-24 21:43:33，当前版本为作者最后更新于2020-02-26 20:18:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简述

• 给你一个无向图，有一些点坏了。
• 已知一些点没有坏，但是无法不经过坏点到达（以下简称为无法到达） $1$ 号点。
• 求最少有多少点无法到达 $1$ 号点。

题目分析

特殊点

重点在“没有坏，但是无法到达 $1$ 号点”的 $u$ 点上。

这意味着与它相邻的 $v$点，要么是坏点，要么和它处境一样。

如果 $v$ 是坏点，那与 $v$ 相邻的点有可能能到达 $1$ 号点。

如果 $v$ 和 $u$ 处境一样，那与 $v$ 相邻的点也无法到达 $1$ 号点。

所以最好的假设是与 $u$ 相邻的点全都是坏点。（可以认为是一种贪心）

搜索

刚才已经标记出了所有坏点，然后从 $1$ 号点开始搜索，得到能到达 $1$ 号点的点的数量。

用总点数减去搜出来的答案，得到无法到达的点的数量

代码

#include<iostream>
#include<vector>
using namespace std;
int p,c,n,ans;//ans表示搜到的点的数量
bool broken[30010];//需不需要被搜索
vector<int>edge[30010];//边
void dfs(int x){
	ans++;//搜到的点又多了一个
	broken[x]=true;//下次别再搜这个点了
	for(int i=0;i<edge[x].size();i++){
		int y=edge[x][i];//能使代码清晰一点
		if(!broken[y])dfs(y);//不让你搜就别搜
	}
}
int main(){
	cin>>p>>c>>n;
	for(int i=1;i<=c;i++){
		int x,y;cin>>x>>y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		for(int j=0;j<edge[x].size();j++)
			broken[edge[x][j]]=true;//与之相邻，都不要被搜
	}
	dfs(1);
	cout<<p-ans<<endl;
    return 0;
}

后记

还有一些问题可以想一想：

• $u$ 点不能被搜到，为什么不标记？
• 如果 $v$ 点也是已知的“没有坏，但是无法不经过坏点到达 $1$ 号点”的点，算法会不会出错？

这些问题插在中间可能会打断思路，所以放在最后。

• 因为相邻的点都被标记了，不可能被搜到。
• 因为我们能确定与 $v$ 相邻的点都不能到达 $1$ 号点，所以 $v$ 与世隔绝，$v$ 被误判成坏点也不重要了。