[BZOJ4326][codevs4632][codevs5440][UOJ#150][NOIP2015]运输计划

2023-07-24 11:52:28

试题描述

公元 2044 年，人类进入了宇宙纪元。

L 国有 n 个星球，还有 n−1 条双向航道，每条航道建立在两个星球之间，这 n−1 条航道连通了 L 国的所有星球。

小 P 掌管一家物流公司，该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 j，任意飞船驶过它所花费的时间为 tj，并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新， L 国国王同意小 P 的物流公司参与 L 国的航道建设，即允许小P 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后，这 m 个运输计划会同时开始，所有飞船一起出发。当这 m 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。

如果小 P 可以*选择将哪一条航道改造成虫洞，试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少？

输入

第一行包括两个正整数 n,m，表示 L 国中星球的数量及小 P 公司预接的运输计划的数量，星球从 1 到 n 编号。

接下来 n−1 行描述航道的建设情况，其中第 i 行包含三个整数 ai,bi 和 ti，表示第 i 条双向航道修建在 ai 与 bi 两个星球之间，任意飞船驶过它所花费的时间为 ti。数据保证 1≤ai,bi≤n 且 0≤ti≤1000。

接下来 m 行描述运输计划的情况，其中第 j 行包含两个正整数 uj 和 vj，表示第 j 个运输计划是从 uj 号星球飞往 vj号星球。数据保证 1≤ui,vi≤n

输出

输出文件只包含一个整数，表示小 P 的物流公司完成阶段性工作所需要的最短时间。

输入示例

输出示例

数据规模及约定

测试点编号	n=	m=	约定
1	100	1
2	100	100	第i条航道连接i号星球与i+1号星球
3	100	100
4	2000	1
5	1000	1000	第i条航道连接i号星球与i+1号星球
6	2000	2000	第i条航道连接i号星球与i+1号星球
7	3000	3000	第i条航道连接i号星球与i+1号星球
8	1000	1000
9	2000	2000
10	3000	3000
11	80000	1
12	100000	1
13	70000	70000	第i条航道连接i号星球与i+1号星球
14	80000	80000	第i条航道连接i号星球与i+1号星球
15	90000	90000	第i条航道连接i号星球与i+1号星球
16	100000	100000	第i条航道连接i号星球与i+1号星球
17	80000	80000
18	90000	90000
19	100000	100000
20	300000	300000
所有数据			1<=ai,bi,uj,vj<=n,0<=ti<=1000

题解

留了好久的坑终于填上了。我们首先把每条链（即每个运输计划）的长度预处理出来，然后按照长度从大到小排序。

因为我们发现如果想使答案减小，一定要让最长的链变短。我们需要将所有链长相同的链进行合并（即求交，不难发现多条链只要有交集，那么交集就是一条链），然后重复一下过程：

1.) 对当前链找到它的边长最大值 mx，用 max{ 下一链长, 当前链长 - mx } 更新答案 ans；

2.) 把下一条链与当前链合并（求交），作为下一轮的当前链；

3.) 若这不是最后一条链，回到 1.)。

4.) 最后答案就是 ans。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

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 600010

#define maxlog 20

#define oo 2147483647

int n, m, q, head[maxn], next[maxm], to[maxm], dist[maxm];

struct Que {

	int a, b, d;

	Que() {}

	Que(int _1, int _2, int _3): a(_1), b(_2), d(_3) {}

	bool operator < (const Que& t) const { return d > t.d; }

} qs[maxn];

void AddEdge(int a, int b, int c) {

	to[++m] = b; dist[m] = c; next[m] = head[a]; head[a] = m;

	swap(a, b);

	to[++m] = b; dist[m] = c; next[m] = head[a]; head[a] = m;

	return ;

}

int dep[maxn], Dep[maxn], fa[maxlog][maxn], mx[maxlog][maxn], L[maxn], R[maxn], clo, list[maxm], cl, pos[maxn];

void build(int u) {

	L[u] = ++clo; list[++cl] = u; pos[u] = cl;

	for(int i = 1; i < maxlog; i++) {

		int v = fa[i-1][u];

		fa[i][u] = fa[i-1][v];

		mx[i][u] = max(mx[i-1][u], mx[i-1][v]);

	}

	for(int e = head[u]; e; e = next[e]) if(to[e] != fa[0][u]) {

		fa[0][to[e]] = u;

		mx[0][to[e]] = dist[e];

		dep[to[e]] = dep[u] + 1;

		Dep[to[e]] = Dep[u] + dist[e];

		build(to[e]);

		list[++cl] = u;

	}

	R[u] = clo;

	return ;

}

int Log[maxm], Lca[maxlog][maxm];

void rmq_init() {

	Log[1] = 0;

	for(int i = 2; i <= cl; i++) Log[i] = Log[i>>1] + 1;

	for(int i = 1; i <= cl; i++) Lca[0][i] = list[i];

	for(int j = 1; (1 << j) <= cl; j++)

		for(int i = 1; i + (1 << j) - 1 <= cl; i++) {

			int a = Lca[j-1][i], b = Lca[j-1][i+(1<<j-1)];

			Lca[j][i] = dep[a] < dep[b] ? a : b;

		}

	return ;

}

int lca(int a, int b) {

	int l = min(pos[a], pos[b]), r = max(pos[a], pos[b]), t = Log[r-l+1];

	a = Lca[t][l]; b = Lca[t][r-(1<<t)+1];

	return dep[a] < dep[b] ? a : b;

}

int calc(int a, int b) {

	return Dep[a] + Dep[b] - (Dep[lca(a,b)] << 1);

}

int calcmx(int a, int b) {

	if(dep[a] < dep[b]) swap(a, b);

	int Mx = 0;

	for(int i = maxlog-1; i >= 0; i--) if(dep[a] - (1 << i) >= dep[b])

		Mx = max(Mx, mx[i][a]), a = fa[i][a];

	for(int i = maxlog-1; i >= 0; i--) if(fa[i][a] != fa[i][b])

		Mx = max(Mx, max(mx[i][a], mx[i][b])),

		a = fa[i][a], b = fa[i][b];

	return a == b ? Mx : max(Mx, max(mx[0][a], mx[0][b]));

}

bool cmp(int a, int b) { return dep[a] > dep[b]; }

bool isson(int pa, int son) { return L[pa] <= L[son] && L[son] <= R[pa]; }

int main() {

	n = read(); q = read();

	for(int i = 1; i < n; i++) {

		int a = read(), b = read(), c = read();

		AddEdge(a, b, c);

	}

	build(1); rmq_init();

	for(int i = 1; i <= q; i++) {

		int u = read(), v = read();

		qs[i] = Que(u, v, calc(u, v));

	}

	sort(qs + 1, qs + q + 1);

//	for(int i = 1; i <= q; i++) printf("%d %d %d %d\n", qs[i].a, qs[i].b, qs[i].d, lca(qs[i].a, qs[i].b));

	int A = qs[1].a, B = qs[1].b, ans = oo;

//	printf("%d %d(%d %d)\n", qs[2].d, calcmx(A, B), A, B);

	if(qs[1].d != qs[2].d || q == 1)

		ans = min(ans, max(qs[2].d, qs[1].d - calcmx(A, B)));

	for(int i = 2; i <= q; i++) {

		int a = qs[i].a, b = qs[i].b, C = lca(A, B);

		int ps[10];

		ps[1] = lca(a, A); ps[2] = lca(a, B); ps[3] = lca(a, b);

		ps[4] = lca(b, A); ps[5] = lca(b, B); ps[6] = lca(A, B);

		sort(ps + 1, ps + 7, cmp);

		int cp = unique(ps + 1, ps + 7) - ps;

		A = ps[1]; B = ps[2];

		bool ok = 1;

		for(int j = 3; j <= cp; j++)

			if(!isson(ps[j], A) || !isson(ps[j], B)) {

				ok = 0; break;

			}

		if(!ok) break;

		if(qs[i].d != qs[i+1].d || i == q)

			ans = min(ans, max(qs[i+1].d, qs[1].d - calcmx(A, B)));

//		printf("[%d %d]\n", A, B);

	}

	printf("%d\n", ans);

	return 0;

}

2016-10-29 uoj 上自己 hack 自己成功，下面是 AC 代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

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 600010

#define maxlog 20

#define oo 2147483647

int n, m, q, head[maxn], next[maxm], to[maxm], dist[maxm];

struct Que {

    int a, b, d;

    Que() {}

    Que(int _1, int _2, int _3): a(_1), b(_2), d(_3) {}

    bool operator < (const Que& t) const { return d > t.d; }

} qs[maxn];

void AddEdge(int a, int b, int c) {

    to[++m] = b; dist[m] = c; next[m] = head[a]; head[a] = m;

    swap(a, b);

    to[++m] = b; dist[m] = c; next[m] = head[a]; head[a] = m;

    return ;

}

int dep[maxn], Dep[maxn], fa[maxlog][maxn], mx[maxlog][maxn], L[maxn], R[maxn], clo, list[maxm], cl, pos[maxn];

void build(int u) {

    L[u] = ++clo; list[++cl] = u; pos[u] = cl;

    for(int i = 1; i < maxlog; i++) {

        int v = fa[i-1][u];

        fa[i][u] = fa[i-1][v];

        mx[i][u] = max(mx[i-1][u], mx[i-1][v]);

    }

    for(int e = head[u]; e; e = next[e]) if(to[e] != fa[0][u]) {

        fa[0][to[e]] = u;

        mx[0][to[e]] = dist[e];

        dep[to[e]] = dep[u] + 1;

        Dep[to[e]] = Dep[u] + dist[e];

        build(to[e]);

        list[++cl] = u;

    }

    R[u] = clo;

    return ;

}

int Log[maxm], Lca[maxlog][maxm];

void rmq_init() {

    Log[1] = 0;

    for(int i = 2; i <= cl; i++) Log[i] = Log[i>>1] + 1;

    for(int i = 1; i <= cl; i++) Lca[0][i] = list[i];

    for(int j = 1; (1 << j) <= cl; j++)

        for(int i = 1; i + (1 << j) - 1 <= cl; i++) {

            int a = Lca[j-1][i], b = Lca[j-1][i+(1<<j-1)];

            Lca[j][i] = dep[a] < dep[b] ? a : b;

        }

    return ;

}

int lca(int a, int b) {

    int l = min(pos[a], pos[b]), r = max(pos[a], pos[b]), t = Log[r-l+1];

    a = Lca[t][l]; b = Lca[t][r-(1<<t)+1];

    return dep[a] < dep[b] ? a : b;

}

int calc(int a, int b) {

    return Dep[a] + Dep[b] - (Dep[lca(a,b)] << 1);

}

int calcmx(int a, int b) {

    if(dep[a] < dep[b]) swap(a, b);

    int Mx = 0;

    for(int i = maxlog-1; i >= 0; i--) if(dep[a] - (1 << i) >= dep[b])

        Mx = max(Mx, mx[i][a]), a = fa[i][a];

    for(int i = maxlog-1; i >= 0; i--) if(fa[i][a] != fa[i][b])

        Mx = max(Mx, max(mx[i][a], mx[i][b])),

        a = fa[i][a], b = fa[i][b];

    return a == b ? Mx : max(Mx, max(mx[0][a], mx[0][b]));

}

bool cmp(int a, int b) { return dep[a] > dep[b]; }

bool isson(int pa, int son) { return L[pa] <= L[son] && L[son] <= R[pa]; }

bool on(int u, int pa, int son) { return isson(u, son) & isson(pa, u); }

int main() {

    n = read(); q = read();

    for(int i = 1; i < n; i++) {

        int a = read(), b = read(), c = read();

        AddEdge(a, b, c);

    }

    build(1); rmq_init();

    for(int i = 1; i <= q; i++) {

        int u = read(), v = read();

        qs[i] = Que(u, v, calc(u, v));

	}

	sort(qs + 1, qs + q + 1);

//	for(int i = 1; i <= q; i++) printf("%d %d %d %d\n", qs[i].a, qs[i].b, qs[i].d, lca(qs[i].a, qs[i].b));

	int A = qs[1].a, B = qs[1].b, ans = qs[1].d;

//	printf("%d %d(%d %d)\n", qs[2].d, calcmx(A, B), A, B);

	if(qs[1].d != qs[2].d || q == 1)

		ans = min(ans, max(qs[2].d, qs[1].d - calcmx(A, B)));

	for(int i = 2; i <= q; i++) {

		int a = qs[i].a, b = qs[i].b;

		int a1 = a, b1 = b, c1 = lca(a1, b1), a2 = A, b2 = B, c2 = lca(a2, b2);

		if((on(a2, c1, a1) && a2 != c1) || (on(b2, c1, a1) && b2 != c1) || (on(c2, c1, a1) && c2 != a1)

		|| (on(a2, c1, b1) && a2 != c1) || (on(b2, c1, b1) && b2 != c1) || (on(c2, c1, b1) && c2 != b1)

		|| (on(a1, c2, a2) && a1 != c2) || (on(b1, c2, a2) && b1 != c2) || (on(c1, c2, a2) && c1 != a2)

		|| (on(a1, c2, b2) && a1 != c2) || (on(b1, c2, b2) && b1 != c2) || (on(c1, c2, b2) && c1 != b2)) ;

		else break;

		int ps[10];

		ps[1] = lca(a, A); ps[2] = lca(a, B); ps[3] = lca(a, b);

		ps[4] = lca(b, A); ps[5] = lca(b, B); ps[6] = lca(A, B);

		sort(ps + 1, ps + 7, cmp);

		int cp = unique(ps + 1, ps + 7) - ps;

		A = ps[1]; B = ps[2];

		bool ok = 1;

		for(int j = 3; j <= cp; j++)

			if(!isson(ps[j], A) || !isson(ps[j], B)) {

				ok = 0; break;

			}

		if(!ok) break;

		if(qs[i].d != qs[i+1].d || i == q)

			ans = min(ans, max(qs[i+1].d, qs[1].d - calcmx(A, B)));

		if(qs[i].d != qs[i+1].d || i == q)

			ans = min(ans, max(qs[i+1].d, qs[1].d - calcmx(A, B)));

//		printf("[%d %d]\n", A, B);

    }

    printf("%d\n", ans);

    return 0;

}

码农公寓

相关文章