bzoj1060
题目描述：小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在且仅存在一条通路（通路指连接两个元件的导线序列）。在电路板上存在一个特殊的元件称为“激发器”。当激发器工，产生一个激励电流，通过导线传向每一个它所连接的节点。而中间节点接收到激励电流后，得到信息，并将该激励流传向与它连接并且尚未接收到激励电流的节点。最终，激烈电流将到达一些“终止节点”——接收激励电流之后不再转发的节点。激励电流在导线上的传播是需要花费时间的，对于每条边e，激励电流通过它需要的时间为te，而节点接收到激励电流后的转发可以认为是在瞬间完成的。现在这块电路板要求每一个“终止节点”同时得到激励电路——即保持时态同步。由于当前的构造并不符合时态同步的要求，故需要通过改变连接线的构造。目前小Q有一个道具，使用一次该道具，可以使得激励电流通过某条连接导线的时间增加一个单位。请问小Q最少使用多少次道具才可使得所有的“终止节点”时态同步？
输入格式：第一行包含一个正整数N，表示电路板中节点的个数。第二行包含一个整数S，为该电路板的激发器的编。接下来N-1行，每行三个整数a , b , t。表示该条导线连接节点a与节点b，且激励电流通过这条导线需要t个单位时间
输出格式：仅包含一个整数V，为小Q最少使用的道具次数。
输入样例： 3 1 1 2 1 1 3 3
输出样例： 2
解析：听说是树形DP，但感觉一看就是个贪心啊。 最后点的时间大小肯定是耗时最多的点的大小，所以先一次dfs找出耗时最大的点的大小。 再对于每个点处理出它的子树内还需要加的单位的最小值。 最后从根向叶子dfs一遍贪心累加就好了。 细节看代码。
代码如下：
#include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn = 500005; int n, s; int hed[maxn << 1], nxt[maxn << 1], to[maxn << 1], val[maxn << 1], cnt; ll dep[maxn], tim, size[maxn], ans; int read(void) { char c; while (c = getchar(), c < '0' || c >'9'); int x = c - '0'; while (c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; return x; } void add(int x, int y, int v) { nxt[++ cnt] = hed[x]; hed[x] = cnt; to[cnt] = y; val[cnt] = v; } void dfs(int u, int pre) { //找出深度最大的点 for (int i = hed[u]; i ; i = nxt[i]) { int v = to[i]; if (v == pre) continue; dep[v] = dep[u] + val[i]; dfs(v, u); } } void dfs1(int u, int pre) { //处理出每个子树中所需加上单位的最小值 int flag = 0; for (int i = hed[u]; i ; i = nxt[i]) { int v = to[i]; if (v == pre) continue; dfs1(v, u); flag = 1; size[u] = min(size[u], size[v]); } if (!flag) size[u] = tim - dep[u]; } void dfs2(int u, int pre, int add) { //add记录下已经加了多少个单位 for (int i = hed[u]; i ; i = nxt[i]) { int v = to[i]; if (v == pre) continue; if (size[v] - add > 0) { //若现在加上的单位还不够多，就继续加 ans += size[v] - add; dfs2(v, u, size[v]); } else dfs2(v, u, add); } } int main() { n = read(); s = read(); for (int i = 1; i < n; ++ i) { int x = read(), y = read(), v = read(); add(x, y, v); add(y, x, v); } dfs(s, 0); for (int i = 1; i <= n; ++ i) if (dep[i] > tim) tim = dep[i]; for (int i = 1; i <= n; ++ i) size[i] = 2e9; dfs1(s, 0); dfs2(s, 0, 0); printf("%lld", ans); return 0;转载于:https://www.cnblogs.com/Gaxc/p/10016549.html
相关资源：JAVA上百实例源码以及开源项目