AOJ 795.西瓜理发记(三)

149


题目


点击显/隐题目

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





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





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





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





4





题解


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

根据这个思路来分析每一个节点
可以发现:
  1. 如果从一个节点的子节点已经有 a 个朋友清扫,那么从该节点到树根都不需要再找朋友清扫
  2. 如果该节点的所有子节点都没有朋友清扫,那么如果从该节点到树根有需要清扫的路,只需要找一个朋友清扫即可

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

dp[i] 表示从叶子到第 i 个节点的所需要最少的朋友数, dp[1] 即为答案
dp[i] = sum{ max(dp[j],Need_Clean) } 其中 ji 的所有子节点, 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.syncwithstdio(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;icin>>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;
}
}
发布评论
  • 点击查看/关闭被识别为广告的评论