[BZOJ2282][Sdoi2011]消防
试题描述
某个国家有n个城市，这n个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为zi(zi<=1000)。
这个国家的人对火焰有超越宇宙的热情，所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍（大量的消防经费开销）可是却又无可奈何（总统竞选的国民支持率），所以只能想尽方法提高消防能力。
现在这个国家的经费足以在一条边长度和不超过s的路径（两端都是城市）上建立消防枢纽，为了尽量提高枢纽的利用率，要求其他所有城市到这条路径的距离的最大值最小。
你受命监管这个项目，你当然需要知道应该把枢纽建立在什么位置上。
输入
输入包含n行：第1行，两个正整数n和s，中间用一个空格隔开。其中n为城市的个数，s为路径长度的上界。设结点编号以此为1，2，……，n。从第2行到第n行，每行给出3个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，“2 4 7”表示连接结点2与4的边的长度为7。
输出
输出包含一个非负整数，即所有城市到选择的路径的最大值，当然这个最大值必须是所有方案中最小的。
输入示例
5 21 2 52 3 22 4 42 5 3
输出示例
5
数据规模及约定
对于100%的数据，n<=300000，边长小等于1000。
题解
推理一下发现选择的两个点肯定在树的直径上，那么我们可以二分答案 x（显然二分的下界是所有叶子节点到直径距离的最大值），从直径的两个端点向内走小于等于 x 的最大长度，然后看这两个点的距离是否小于等于题目描述中的 s。
这道傻逼题边权有可能为 0，于是可能出现奇奇怪怪的错误，比如在找直径的时候不能用判断 d[u] = d[to[e]] + dist[e] 的方法。
#include#include #include #include using namespace std;const int BufferSize = 1 << 16;char buffer[BufferSize], *Head, *Tail;inline char Getchar() { if(Head == Tail) { int l = fread(buffer, 1, BufferSize, stdin); Tail = (Head = buffer) + l; } return *Head++;}int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); } return x * f;}#define maxn 300010#define maxm 600010int n, m, head[maxn], nxt[maxm], to[maxm], dist[maxm], lim, A, B;void AddEdge(int a, int b, int c) { to[++m] = b; dist[m] = c; nxt[m] = head[a]; head[a] = m; swap(a, b); to[++m] = b; dist[m] = c; nxt[m] = head[a]; head[a] = m; return ;}int Q[maxn], hd, tl, d[maxn], fa[maxn], fad[maxn];void bfs() { while(hd < tl) { int u = Q[++hd]; for(int e = head[u]; e; e = nxt[e]) if(d[to[e]] < 0) { d[to[e]] = d[u] + dist[e]; fa[to[e]] = u; fad[to[e]] = dist[e]; Q[++tl] = to[e]; } } return ;}int diap[maxn], dis[maxn], cntd;bool check(int x) { int l = 1, r = cntd, tmp = x; while(x && l < cntd) { if(x < dis[l+1] - dis[l]) break; x -= dis[l+1] - dis[l]; l++; } while(tmp && r > 1) { if(tmp < dis[r] - dis[r-1]) break; tmp -= dis[r] - dis[r-1]; r--; }// printf("%d: %d %d\n", ttmp, diap[l], diap[r]); return dis[r] - dis[l] <= lim;}int main() { n = read(); lim = read(); for(int i = 1; i < n; i++) { int a = read(), b = read(), c = read(); AddEdge(a, b, c); } memset(d, -1, sizeof(d)); hd = tl = 0; Q[++tl] = 1; d[1] = 0; bfs(); for(int i = 1; i <= n; i++) if(d[A] < d[i]) A = i; memset(d, -1, sizeof(d)); hd = tl = 0; Q[++tl] = A; d[A] = 0; bfs(); for(int i = 1; i <= n; i++) if(d[B] < d[i]) B = i;// printf("%d %d\n", A, B); int u = B; diap[++cntd] = u; dis[cntd] = 0; while(u != A) { diap[++cntd] = fa[u]; dis[cntd] = dis[cntd-1] + fad[u]; u = fa[u]; }// for(int i = 1; i <= cntd; i++) printf("%d(%d)%c", diap[i], dis[i], i < cntd ? ' ' : '\n'); int l = 0, r = d[B]; memset(d, -1, sizeof(d)); hd = tl = 0; for(int i = 1; i <= cntd; i++) Q[++tl] = diap[i], d[diap[i]] = 0; bfs(); for(int i = 1; i <= n; i++) l = max(l, d[i]); while(l < r) { int mid = l + r >> 1; if(!check(mid)) l = mid + 1; else r = mid; } printf("%d\n", l); return 0;}