NOIP2013 Day1 T3(最大生成树+树链剖分/最大生成树+倍增)

一看题目就想树剖,但是这里是图,怎么办?用最小生成树。我们只需要用最大的那几条边来连接这些点成为一棵树,其他的边是没有用的。求完最大树以后,再树链剖分或者倍增思想,这里没有做倍增只做了树剖,注意树剖的时候边权转点权,边权放到深度深的那个点上,然后处理每一个路径$(u,v)$,对于$LCA(u,v)$是不用加的!刚开始正解和暴力全部写挂这里直接10分。改了之后发现暴力还比正解快500ms。。下面给出树剖代码和暴力代码,以及数据生成器,有用的可以拿去。

树剖:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;

const int MAXN = 10000 + 5, MAXM = 50000 + 5, INF = 1000000000;

struct data1 {
    int u, v, wi;
    bool operator < (const data1 &x) const {
        return wi > x.wi;
    }
}e1[MAXM];//原图 
struct data2 {
    int v, wi;
}e2[MAXM*2];//最大树 

int n, m, Q, en, f[MAXN];//最大树边数,并查集 
int dwi[MAXN], dep[MAXN], fa[MAXN], top[MAXN], p[MAXN], siz[MAXN], son[MAXN], pre;//树剖
int minv[MAXN*4];//线段树 
vector<int> G[MAXN];//最大树

#define lc (o<<1)
#define rc (o<<1|1)
#define M ((l+r)>>1)
void pushup(int o) {//线段树 
    minv[o] = min(minv[lc], minv[rc]);
}
void update(int o, int l, int r, int p, int v) {//线段树 
    if (l==r) {
        minv[o] = v;
        return ;
    }
    if (p<=M) update(lc, l, M, p, v); 
        else if (M<p) update(rc, M+1, r, p, v);
    pushup(o);
}
int query(int o, int l, int r, int x, int y) {//线段树 
    int ret = INF;
    if (x<=l&&r<=y) {
        return minv[o];
    }
    if (x<=M) ret = min(ret, query(lc, l, M, x, y)); 
    if (M<y)  ret = min(ret, query(rc, M+1, r, x, y));
    return ret;
}
int find(int x) {return x==f[x] ? x : f[x] = find(f[x]);}//并查集find 
void dfs1(int u, int pa) {//树剖 
    dep[u] = dep[pa] + 1, fa[u] = pa, siz[u] = 1;
    for (int i=0;i<G[u].size();i++) {
        data2 d2 = e2[G[u][i]];
        int v = d2.v, wi = d2.wi;
        if (v!=pa) {
            dfs1(v, u);
            dwi[v] = wi;
            siz[u] += siz[v];
            if (son[u]==-1||siz[v]>siz[son[u]]) son[u] = v;
        }
    }
}
void dfs2(int u, int cha) {//树剖 
    top[u] = cha, p[u] = ++pre;
    if (son[u]!=-1) {
        dfs2(son[u], cha);
        for (int i=0;i<G[u].size();i++) {
            data2 d2 = e2[G[u][i]];
            int v = d2.v;
            if (v!=fa[u]&&v!=son[u]) {
                dfs2(v, v);
            }
        }
    }
}
int findMax(int u, int v) {//树剖 
    int ret = INF, f1 = top[u], f2 = top[v];
    while (f1!=f2) {
        if (dep[f1]<dep[f2]) swap(f1, f2), swap(u, v);
        ret = min(ret, query(1,1,n,p[f1],p[u]));
        u = fa[f1];
        f1 = top[u];
    }
    if (dep[u]<dep[v]) swap(u, v);
    return min(ret, query(1,1,n,p[v]+1,p[u]));
}
void MST() {//Kruskal 
    sort(e1+1, e1+1+m);
    for (int i=1;i<=m;i++) {
        int a1 = find(e1[i].u), b1 = find(e1[i].v);
        if (a1==b1) continue;
        f[a1] = b1;
        en++, e2[en].v = e1[i].v, e2[en].wi = e1[i].wi, G[e1[i].u].push_back(en);
        en++, e2[en].v = e1[i].u, e2[en].wi = e1[i].wi, G[e1[i].v].push_back(en);
    }
}
void clean() {
    pre = en = 0;
    for (int i=0;i<=n;i++) {
        dep[i] = fa[i] = top[i] = p[i] = siz[i] = 0;
        son[i] = -1;
        f[i] = i;
        G[i].clear();
    }
    for (int i=0;i<=4*n;i++) minv[i] = INF;
}
void init() {
    clean();
    for (int i=1;i<=m;i++) {
        scanf("%d%d%d", &e1[i].u, &e1[i].v, &e1[i].wi);
    }
}
void solve() {
    MST();
    for (int i=1;i<=n;i++) if (!dep[i]) dfs1(i, 0);
    for (int i=1;i<=n;i++) if (!p[i]) dfs2(i, i);
    for (int i=1;i<=n;i++) if (fa[i]!=0) update(1,1,n,p[i],dwi[i]);
    scanf("%d", &Q);
    for (int i=1;i<=Q;i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        int a1 = find(u), b1 = find(v);
        if (a1!=b1) {printf("-1\n"); continue;}
        printf("%d\n", findMax(u, v));
    }
}
int main() {
    #ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    while (scanf("%d%d", &n, &m)==2) init(), solve();
    return 0;
}

暴力:(跑得比树剖还快)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;

const int MAXN = 10000 + 5, MAXM = 50000 + 5, INF = 1000000000;

struct data1 {
    int u, v, wi;
    bool operator < (const data1 &x) const {
        return wi > x.wi;
    }
}e1[MAXM];//原图 
struct data2 {
    int v, wi;
}e2[MAXM*2];//最大树 

vector<int> G[MAXN];//最大树
int dwi[MAXN], en, n, m, dep[MAXN], fa[MAXN], f[MAXN];

void dfs(int u, int pa) {
    dep[u] = dep[pa] + 1, fa[u] = pa;
    for (int i=0;i<G[u].size();i++) {
        data2 d2 = e2[G[u][i]];
        int v = d2.v;
        if (v!=fa[u]) {
            dfs(v, u);
            dwi[v] = d2.wi;
        }
    }
}
int find(int x) {return x==f[x] ? x : f[x] = find(f[x]);}//并查集find
void MST() {//Kruskal 
    sort(e1+1, e1+1+m);
    for (int i=1;i<=m;i++) {
        int a1 = find(e1[i].u), b1 = find(e1[i].v);
        if (a1==b1) continue;
        f[a1] = b1;
        en++, e2[en].v = e1[i].v, e2[en].wi = e1[i].wi, G[e1[i].u].push_back(en);
        en++, e2[en].v = e1[i].u, e2[en].wi = e1[i].wi, G[e1[i].v].push_back(en);
    }
}
int findMax(int u, int v) {
    int ret = INF;
    if (dep[u]<dep[v]) swap(u, v);
    while (dep[u]>dep[v]) ret = min(ret, dwi[u]), u = fa[u];
    if (u==v) return ret;
    while (u!=v) ret = min(ret, min(dwi[v], dwi[u])), u = fa[u], v = fa[v];
    return ret; 
}
void clean() {
    en = 0;
    for (int i=0;i<=n;i++) {
        dep[i] = fa[i] = 0;
        f[i] = i;
        G[i].clear();
    }
}
void init() {
    clean();
    for (int i=1;i<=m;i++) {
        scanf("%d%d%d", &e1[i].u, &e1[i].v, &e1[i].wi);
    }
}
void solve() {
    MST();
    for (int i=1;i<=n;i++) if (!dep[i]) dfs(i, 0);
    int Q;
    scanf("%d", &Q);
    for (int i=1;i<=Q;i++) {
        int u, v;
        scanf("%d%d", &u ,&v);
        int a1 = find(u), b1 = find(v);
        if (a1!=b1) {printf("-1\n"); continue;}
        printf("%d\n", findMax(u, v));
    }
}
int main() {
    #ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);freopen("2.out", "w", stdout);
    #endif
    while (scanf("%d%d", &n, &m)==2) init(), solve();
    return 0;
}

数据生成器:

#include<cstdio>
#include<algorithm>
#include<windows.h>
#include<winbase.h>
#include<set>
using namespace std;

int n = 3, m = 5, w = 5, q = 3;
int main() {
    freopen("1.in", "w", stdout);
    srand(GetTickCount());
    printf("%d %d\n", n, m); 
    for (int i=1;i<=m;i++) {
        int a = rand()%n+1;
        int b = rand()%n+1;
        while (a==b) b = rand()%n+1;
        printf("%d %d %d\n", a, b, rand()%w); 
    }
    printf("%d\n", q); 
    for (int i=1;i<=q;i++) {
        int a = rand()%n+1;
        int b = rand()%n+1;
        while (a==b) b = rand()%n+1;
        printf("%d %d\n", a, b); 
    }
    return 0;
}
------ 本文结束 ------