BZOJ1060 - [ZJOI2007]时态同步

2016/11/22

题目

小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成,我们不妨称之为节点,并将其用数 字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接,且对于电路板的任何两个节点,都存在且仅 存在一条通路(通路指连接两个元件的导线序列)。在电路板上存在一个特殊的元件称为“激发器”。当激发器工 作后,产生一个激励电流,通过导线传向每一个它所连接的节点。而中间节点接收到激励电流后,得到信息,并将 该激励电流传向与它连接并且尚未接收到激励电流的节点。最终,激烈电流将到达一些“终止节点”——接收激励 电流之后不再转发的节点。激励电流在导线上的传播是需要花费时间的,对于每条边e,激励电流通过它需要的时 间为te,而节点接收到激励电流后的转发可以认为是在瞬间完成的。现在这块电路板要求每一个“终止节点”同时 得到激励电路——即保持时态同步。由于当前的构造并不符合时态同步的要求,故需要通过改变连接线的构造。目 前小Q有一个道具,使用一次该道具,可以使得激励电流通过某条连接导线的时间增加一个单位。请问小Q最少使用 多少次道具才可使得所有的“终止节点”时态同步?

解法

树形DP,直接把较短的路径都弄成最长路径那么长。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
using namespace std;
typedef long long LL;
const int PSIZ = (500000<<1) + 1000;
int N, S; LL ans;

struct tgno {
    int u, v, w; tgno* n;
} POOL[PSIZ]; int ppos;
tgno* Head[PSIZ];

void _add(int u, int v, int w) {
    POOL[ppos].u = u; POOL[ppos].v = v;
    POOL[ppos].w = w; POOL[ppos].n = Head[u];
    Head[u] = &POOL[ppos++];
}

void addEdge(int u, int v, int w) {
    _add(u, v, w); _add(v, u, w);
}

int sdep[PSIZ]; // 数据有误,int可过全部样例
void dfslen(int cur, int pre) {
    typedef tgno* It;

    for(It i=Head[cur];i;i=i->n) {
        if(i->v != pre) {
            dfslen(i->v, cur);
            sdep[cur] = max(sdep[cur], sdep[i->v] + i->w);
        }
    }

    for(It i=Head[cur];i;i=i->n) {
        if(i->v != pre) {
            ans += sdep[cur] - i->w - sdep[i->v];
        }
    }
}

int main() {
    cin >> N >> S;
    int u, v, w;
    for(int i=1;i<N;i++) {
        cin >> u >> v >> w;
        addEdge(u, v, w);
    }
    dfslen(S, 0);
    cout << ans << endl;
}