题解 P2899 【[USACO08JAN]手机网络Cell Phone Network】

InnovatorNZ · 2017-11-03 17:28:51 · 题解

做法都在注释里了

每次dfs里面都有三种状态：-1,0,1

-1表示要让自己的父亲放天线

0表示自己不用放天线，不过也不用父亲放天线了，因为儿子帮你放好了

1表示自己不得不放天线，即要帮爹（也表示自己被坑了）

别的都看代码的注释就好了（可能是史上最滑稽的注释）

#include <iostream>
#include <vector>
using namespace std;
#define maxn 100001
int n; 
int ans=0;
vector<int> conn_matrix[maxn];       //邻接表
int dfs(int u, int p){
    int chosen=-1;    //初始值
    for(auto val:conn_matrix[u]){    //循环每个邻居（儿子&父亲）
        if(val!=p){      //如果当前的val不是父亲，也就是说要对每个儿子枚举，但不包括父亲
            int ret=dfs(val, u);    //看儿子是啥状态
            if(ret==-1)        //如果儿子说要坑爹
                chosen=1;    //那么身为父亲的自己一定要立天线，即要帮爹
            else if(ret==1 && chosen!=1)    //如果儿子说“我要帮你了，我帮爹”，并且没有一个坑爹的儿子（其实近似等价于ret==-1）
                chosen=0;    //可以放飞自我了！即不用靠爹，不过也不用天线
        }
    }
    if(chosen==1) ans++;    //要帮爹了，那么ans++
    return chosen;      //返回自己的状态
}
int main(){
    cin>>n;
    for(int i=0; i<n-1; i++){
        int a, b;
        cin>>a>>b;
        conn_matrix[a].push_back(b);
        conn_matrix[b].push_back(a);    //无向图，双向连接
    }
    if(dfs(1, 0)==-1) ans++;    //如果根节点说：我要坑爹！！！但又没爹可坑，那么只能坑自己，自己放一根天线
    cout<<ans<<endl;    //输出答案
    return 0;
}