[NOIP2013]货车运输

OI 题解 LCA MST

算法：LCA, MST

首先建立最大生成树，因为两个节点互相到达必须要经过最大生成树（反证法）。
然后跑LCA+ST就可以了。

代码详解

数据结构:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define il inline
using std::sort;
using std::min;
using std::swap;
const int N = 10000 + 10;
const int M = 2 * 50000 + 10;
const int Q = 2 * 30000 + 10;
const int P = 25;
const int INF = 0x3f3f3f3f;
int n, m, qs;
int head[N], to[M], next[M], v[M], cnt;
int fa[N], rt[N][P], dep[N], st[N][P];
struct edge{
    int from, to, v;
    friend bool operator < (edge a, edge b) {
        return a.v > b.v;
    }
} e[M];

快读:

这里有两种写法
一种是 ans = (ans<<3)+(ans<<1)+(c^`0`), 另一种是ans = ans*10+c-'0', 前者更快（约140ms）。

il int read() {
    char c;
    while(!isdigit(c = getchar()));
    int ans = c ^ '0';//mark: '0' = 0x30;
    while(isdigit(c = getchar())) {
        ans = (ans << 3) + (ans << 1) + (c ^ '0');//mark:二进制要加括号
        //ans = ans * 10 + c - '0';
    }
    return ans;
}

并查集:

il void init() {
    for(register int i = 1; i <= n; ++i)
        fa[i] = i;
}
int find(const int &x) {
    if(fa[x] == x) {
        return fa[x];
    }
    fa[x] = find(fa[x]);
    return fa[x];
}

MST:

il void adde(const int &x, const int &y,const int &z) {
    cnt++;
    to[cnt] = y;
    v[cnt] = z;
    next[cnt] = head[x]; 
    head[x] = cnt;
}
il void kruskal() {
    sort(e + 1, e + m + 1);
    init();
    for(register int i = 1, fx, fy; i <= m; ++i) {
        fx = find(e[i].from);
        fy = find(e[i].to);
        if(fx != fy) {
            adde(e[i].from, e[i].to, e[i].v);
            adde(e[i].to, e[i].from, e[i].v);
            fa[fx] = fy;
        }
    }
}

无根树转有根树:

顺便st表初始化。

void dfs(int pos, int f, int vi) {
//  printf("%d %d %d\n", pos, f, vi);
    rt[pos][0] = f;
    dep[pos] = dep[f] + 1;
    st[pos][0] = vi;
    for(int i = 1; (1 << i) < dep[pos]; ++i) {
//      printf("%d %d\n", pos, i);
        rt[pos][i] = rt[rt[pos][i-1]][i-1];
        st[pos][i] = min(st[rt[pos][i-1]][i-1], st[pos][i-1]);
    }
    for(register int i = head[pos]; i; i = next[i]) {
        if(to[i] != f) {
            dfs(to[i], pos, v[i]);
        }
    }
}

LCA:

倍增算法

il int lca(int x, int y) {
    int ans = INF;
    if(dep[x] > dep[y]) 
        swap(x, y);
    for(int i = 20; i >= 0; --i) {
        if(dep[y] - (1<<i) >= dep[x]) {
            ans = min(ans, st[y][i]);
            y = rt[y][i];
        }   
    }
    if(x == y) return ans;
    for(int i = 20; i >= 0; --i) {
        if(rt[x][i] != rt[y][i]) {
            ans = min( ans, min(st[x][i], st[y][i]) );
            x = rt[x][i];
            y = rt[y][i];
        }
    }
    ans = min( ans, min(st[x][0], st[y][0]) );
    return ans;
}

To be continued:Tarjan

主函数:

int main() {
    n = read();
    m = read();
    for(register int i = 1, x, y, z; i <= m; ++i) {
        e[i].from = read();
        e[i].to = read();
        e[i].v = read();
    }
    memset(st, 0x3f, sizeof st);
    kruskal();
    for(int i = 1; i <= n; ++i) {
        if(!rt[i][0])
            dfs(i, i, 0);
    }
    qs = read();
    for(register int i = 1, x, y; i <= qs; ++i) {
        x = read(); y = read();
        if(find(x) != find(y)) {
            printf("-1\n");
            continue;
        }
        printf("%d\n", lca(x, y));
    }
}

后话

这个题应该还可以用Tarjan实现，未完待续。

听说可以不跑LCA，用SPFA，未完待续。