题解 P2932 【[USACO09JAN]地震造成的破坏Earthquake Damage】

· · 题解

题意简述

题目分析

特殊点

重点在“没有坏，但是无法到达 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;
}

后记

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

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