pac void 纪元 成了 false 链接 ref +=
公元 2044 年,人类进入了宇宙纪元。
L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。
小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物
流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道 是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之 间不会产生任何干扰。
为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小 P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。
在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后, 这 m 个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的 物流公司的阶段性工作就完成了。
如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段 性工作所需要的最短时间是多少
输入文件名为 transport.in。
第一行包括两个正整数 n、m,表示 L 国中星球的数量及小 P 公司预接的运输计划的数量,星球从 1 到 n 编号。
接下来 n-1 行描述航道的建设情况,其中第 i 行包含三个整数 ai, bi 和 ti,表示第
i 条双向航道修建在 ai 与 bi 两个星球之间,任意飞船驶过它所花费的时间为 ti。
接下来 m 行描述运输计划的情况,其中第 j 行包含两个正整数 uj 和 vj,表示第 j个 运输计划是从 uj 号星球飞往 vj 号星球。
输出格式:输出 共1行,包含1个整数,表示小P的物流公司完成阶段性工作所需要的最短时间。
- 6 3
- 1 2 3
- 1 6 4
- 3 1 7
- 4 3 6
- 3 5 5
- 3 6
- 2 5
- 4 5
- 11
所有测试数据的范围和特点如下表所示
请注意常数因子带来的程序效率上的影响。
提供友情暴力+正解分析链接:http://www.cnblogs.com/NaVi-Awson/p/7445989.html
- #include < iostream > #include < cstdio > #include < cstring > #include < algorithm > using namespace std;
- struct Messi {
- int next,
- dis,
- to;
- }
- edge[600110];
- struct ed {
- int p,
- q,
- s;
- }
- plan[300011];
- int head[300011],
- num,
- son[300101],
- size[301001],
- fa[300101],
- dep[300101],
- top[300101],
- pos[300101],
- tot,
- sondis[301001],
- sgm[301001];
- int c1[800011],
- c2[300011],
- n,
- m;
- bool cmp(ed a, ed b) {
- return (a.s < b.s);
- }
- void add(int u, int v, int dis) {
- num++;
- edge[num].next = head[u];
- head[u] = num;
- edge[num].to = v;
- edge[num].dis = dis;
- }
- void dfs1(int u, int pa, int depth) {
- son[u] = 0;
- size[u] = 1;
- fa[u] = pa;
- dep[u] = depth;
- for (int j = head[u]; j; j = edge[j].next) {
- int v = edge[j].to;
- if (v != pa) {
- dfs1(v, u, depth + 1);
- size[u] += size[v];
- if (size[v] > size[son[u]]) son[u] = v,
- sondis[u] = edge[j].dis;
- }
- }
- }
- void dfs2(int u, int tp, int dis) {
- top[u] = tp;
- pos[u] = ++tot;
- sgm[tot] = dis;
- if (son[u]) dfs2(son[u], tp, sondis[u]);
- for (int j = head[u]; j; j = edge[j].next) if (edge[j].to != son[u] && edge[j].to != fa[u]) {
- dfs2(edge[j].to, edge[j].to, edge[j].dis);
- }
- }
- void build(int rt, int l, int r) {
- if (l == r) {
- c1[rt] = sgm[l];
- return;
- }
- int mid = (l + r) / 2;
- build(rt * 2, l, mid);
- build(rt * 2 + 1, mid + 1, r);
- c1[rt] = c1[rt * 2] + c1[rt * 2 + 1];
- }
- int ask(int rt, int l, int r, int L, int R) {
- int x = 0;
- if (l >= L && r <= R) {
- return c1[rt];
- }
- int mid = (l + r) / 2;
- if (L <= mid) x += ask(rt * 2, l, mid, L, R);
- if (R > mid) x += ask(rt * 2 + 1, mid + 1, r, L, R);
- return x;
- }
- int query(int x, int y) {
- int ans = 0;
- while (top[x] != top[y]) {
- if (dep[top[x]] < dep[top[y]]) swap(x, y);
- ans += ask(1, 2, n, pos[top[x]], pos[x]);
- x = fa[top[x]];
- }
- if (dep[x] > dep[y]) swap(x, y);
- if (x != y) ans += ask(1, 2, n, pos[x] + 1, pos[y]);
- return ans;
- }
- void update(int L, int R) {
- c2[L] += 1;
- c2[R + 1] -= 1;
- }
- void change(int x, int y) {
- while (top[x] != top[y]) {
- if (dep[top[x]] < dep[top[y]]) swap(x, y);
- update(pos[top[x]], pos[x]);
- x = fa[top[x]];
- }
- if (dep[x] > dep[y]) swap(x, y);
- if (x != y) update(pos[x] + 1, pos[y]);
- }
- bool check(int x) {
- int i,
- cnt = 0;
- memset(c2, 0, sizeof(c2));
- for (i = m; i >= 1; i--) if (plan[i].s > x) change(plan[i].p, plan[i].q),
- cnt++;
- else break;
- for (i = 1; i <= n; i++) {
- c2[i] += c2[i - 1];
- }
- for (i = 1; i <= n; i++) {
- if (cnt == c2[pos[i]] && plan[m].s - sgm[pos[i]] <= x) return true;
- }
- return false;
- }
- int main() {
- int i,
- x,
- y,
- z,
- maxz = 0,
- l,
- r;
- cin >> n >> m;
- for (i = 1; i <= n - 1; i++) {
- scanf("%d%d%d", &x, &y, &z);
- add(x, y, z);
- add(y, x, z);
- maxz = max(maxz, z);
- }
- dfs1(1, 1, 1);
- dfs2(1, 1, 0);
- build(1, 2, n);
- for (i = 1; i <= m; i++) {
- scanf("%d%d", &plan[i].p, &plan[i].q);
- plan[i].s = query(plan[i].p, plan[i].q);
- }
- sort(plan + 1, plan + 1 + m, cmp);
- r = plan[m].s;
- l = max(0, r - maxz);
- while (l < r) {
- int mid = (l + r) / 2;
- if (check(mid)) r = mid;
- else l = mid + 1;
- }
- cout << l;
- }
NOIP 2015运输计划
来源: http://www.bubuko.com/infodetail-2282320.html