AOJ 795.西瓜理发记(三)|OhYee 博客

这是一篇最后编辑于 8 年前的文章，其内容可能与目前实际情况差异较大，请注意甄别

题目

{% raw %}

{% endraw %} 顺利潜入勺林寺几天后，方丈给了西瓜一个光荣而艰巨的任务——打扫寺庙中的道路。同时给了西瓜一张勺林寺的地图。西瓜这才知道，勺林寺中总共有n座房子，但道路只有n-1条，这n-1条道路连接了寺中的所有房子，即保证在任何两座房子都能沿着道路抵达。好在西瓜人缘不错，他知道每座房子中都有个自己的朋友，只要给他们每个人打个电话，让他到自己这里来，顺便把路也扫了，即给某座房子中的朋友打过电话后，可认为从该房子到西瓜所在的位置之间所有的道路都会被打扫干净。同时西瓜还知道，这n-1条道路中有一些路昨天已经被人打扫过了不需要再打扫一遍。现在西瓜想知道，自己最少要给多少个朋友打电话才能完成方丈给的任务。西瓜在编号为1的房子中。

{% raw %}

{% endraw %}

输入包含多组数据
每组数据第一行包含一个n(2?≤?n?≤?10^5)，表示有n座房子
之后n-1行，每行三个数字a，b，c表示在房子a和房子b之间有一条路，c等于1表示路已被打扫，c等于2表示路未被打扫。

{% raw %}

{% endraw %}

每组数据输出一个整数k，表示最少要给k个朋友打电话

{% raw %}

{% endraw %}

5
1 2 2
1 3 2
1 4 2
1 5 2

{% raw %}

{% endraw %}

题解

根据题意画出图像,可以非常容易发现最终形成一棵以西瓜为树根的树
朋友会一路清扫倒西瓜所在的房间,因此只有住在"树叶"的朋友有可能清扫

根据这个思路来分析每一个节点
可以发现：

如果从一个节点的子节点已经有 a 个朋友清扫,那么从该节点到树根都不需要再找朋友清扫
如果该节点的所有子节点都没有朋友清扫,那么如果从该节点到树根有需要清扫的路,只需要找一个朋友清扫即可

因此可以发现,对于每一个节点,从树叶到该节点所需的最少朋友数只与其子节点有关,符合 动态规划 的特点,属于 树形dp

用 dp[i] 表示从叶子到第 i 个节点的所需要最少的朋友数, dp[1] 即为答案
有 dp[i] = sum{ max(dp[j],Need_Clean) } 其中 j 为 i 的所有子节点, Need_Clean 为道路 (i,j) 是否需要清扫

只需要一个 DFS 即可解决

代码

```cpp 西瓜理发记(三) https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份 #include

#include #include #include using namespace std;

const int maxn = 1e5+5;

struct path{
int u,v;
bool k;
path(int a,int b,int c):u(a),v(b),k(c){}
};
struct Node{
list children;
int father;
};

Node node[maxn];

int dfs(int t){
int ans=0;
for(list::iterator it=node[t].children.begin();it!=node[t].children.end();it++){
int tt = it->v;
if(tt == node[t].father)
continue;
node[tt].father = t;
ans += max(dfs(tt),(int)it->k);
}
return ans;
}

int main(){
cin.tie(0);
cin.sync_with_stdio(false);

int n;
while(cin >> n){
    for(int i=1;i<=n;i++){
        node[i].father=-1;
        node[i].children.clear();
    }
         
    int a,b,c;
    for(int i=1;i<n;i++){
        cin>>a>>b>>c;
        node[a].children.push_back(path(a,b,c-1));
        node[b].children.push_back(path(b,a,c-1));
    }   
    cout << dfs(1) << endl;
}

}

</div>

推荐订阅源

OhYee 博客

题目

题解

代码