VIJOS1983 - [NOIP2015]运输计划

2016/10/29

去年不会写 LCA ,这题爆 0rz。

WA的姿势 (官方数据 65’)

如果想要减小总体时间的话,显然需要把时间最长的给剪掉,所以说直接在最长的任意一条路径上枚举边,然后看一下每条路径有没有经过这条边。

总体复杂度: ,显然要剪枝卡时(事实上只有一个点T掉,其他都是WA。。。)

2016-10-30 更新: 一觉醒来发现一个用 LCA 判覆盖的时候少讨论的 Case,加上之后 80’ ,代码已经修正。

  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
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>
using namespace std;
#ifndef LCYTEST
#   define release(_x) { _x }
#else
#   define release(_x) ;
#endif
typedef long long LL;
typedef pair<int, int> PII;
const int POOL_SIZE = 300000 + 100;
struct tgno {
    int u, v, w;
    tgno* next;
} POOL[POOL_SIZE]; int ppos;
tgno* Head[POOL_SIZE];

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

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

struct task {
    int u, v, lca, dis;
} T[POOL_SIZE];
bool taskcmp(const task &a, const task &b) { return a.dis > b.dis; }

int N, M;
int vis[POOL_SIZE];
int dep[POOL_SIZE], pre[POOL_SIZE][20], dis[POOL_SIZE][20];
void dfs(int curr) {
    typedef tgno* It;
    for(It i=Head[curr];i;i=i->next) {
        if(!dep[i->v]) {
            dep[i->v] = dep[curr] + 1;
            pre[i->v][0] = curr;
            dis[i->v][0] = i->w;
            dfs(i->v);
        }
    }
}

void mkLCA(int root) {
    dep[root] = 1;
    dfs(root);
    for(int j=1;(1<<j)<=N;j++) {
        for(int i=1;i<=N;i++) {
            if(pre[i][j-1]) {
                pre[i][j] = pre[pre[i][j-1]][j-1];
                dis[i][j] = dis[i][j-1] + dis[pre[i][j-1]][j-1];
            }
        }
    }
}

// < LCA, Distance >
PII LCA(int A, int B) {
    int dd = 0, i, j, a = A, b = B;
    if(dep[a] < dep[b]) swap(a, b);
    for(i=0;(1<<i)<=dep[a];i++);
    i--;
    for(j=i;j>=0;j--)
        if(dep[a]-(1<<j)>=dep[b]) {
            dd += dis[a][j]; a = pre[a][j];
        }
    if(a == b) return PII(a, dd);
    for(j=i;j>=0;j--) {
        if(pre[a][j] && pre[a][j] != pre[b][j]) {
            dd += dis[a][j]; a = pre[a][j];
            dd += dis[b][j]; b = pre[b][j];
        }
    }
    return PII(pre[a][0], dd + dis[a][0] + dis[b][0]);
}

int ans = 0;
void ddfs(int s, int f) { // ASSERT! dep[s] >= dep[f]
    while(s != f) {
        int tt = T[0].dis - dis[s][0];
        for(int i=1;i<M;i++) {
            if(T[i].dis < tt) break;
            int a = LCA(s, T[i].u).first;
            int b = LCA(s, T[i].v).first;
//          if(a == T[i].lca && a != s) {
            if(a == T[i].lca && b == s && a != s) { // 2016-10-30
                tt = max(tt, T[i].dis - dis[s][0]);
            } else tt = max(tt, T[i].dis);
        }
        if(tt < ans) { ans = tt; }
        s = pre[s][0];
    }
}

int main() {
    release({
        ios::sync_with_stdio(false); cin.tie(NULL);
    });

    cin >> N >> M;
    int _ = N-1, u, v, w;
    for(int i=0;i<_;i++) {
        cin >> u >> v >> w; addEdge(u, v, w);
    }

    mkLCA(1);

    for(int i=0;i<M;i++) {
        cin >> T[i].u >> T[i].v; if(T[i].u > T[i].v) swap(T[i].u, T[i].v);
        PII p = LCA(T[i].u, T[i].v);
        T[i].lca = p.first; T[i].dis = p.second;
    }

    sort(T, T+M, taskcmp);

    ans = T[0].dis;
    ddfs(T[0].u, T[0].lca);
    ddfs(T[0].v, T[0].lca);

    cout << ans << endl;
}

↑ 以上代码

两种正解

  1. 看起来是个求最大值最小的问题,所以上二分答案。然后用树上差分序列验证(一脸懵B)
  2. %%% XJR 菊苣的做法:

因为我们发现如果想使答案减小,一定要让最长的链变短。我们需要将所有链长相同的链进行合并(即求交,不难发现多条链只要有交集,那么交集就是一条链),然后重复一下过程:
1.) 对当前链找到它的边长最大值 mx,用 max{ 下一链长, 当前链长 - mx } 更新答案 ans;
2.) 把下一条链与当前链合并(求交),作为下一轮的当前链;
3.) 若这不是最后一条链,回到 1.)。
4.) 最后答案就是 ans。

代码如下:

  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
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#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;
}