NOIP2013 货车运输（最大生成树，倍增）

A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。n=1e4,m=5e4.

首先肯定是跑一个最大生成数辣～跑完以后倍增lca即可。注意kruskal的写法，并查集一定要写对！

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=1e4+5, maxm=5e4+5, INF=1e9;

struct Edge{

    int fr, to, next, v;

}e[2*maxn], e1[2*maxm];

bool cmp(const Edge &a, const Edge &b){ return a.v>b.v; }

int cnte, fir[maxn];

void addedge(int x, int y, int v){

    Edge &ed=e[++cnte];

    ed.to=y; ed.next=fir[x]; ed.v=v; fir[x]=cnte;

}

int fa[maxn];

int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]); }

int f[maxn][17], v[maxn][17];  //f表示不包括自己，上面第2^i个结点，v表示从i开始这个路径的权值

int dep[maxn];

void dfs(int now, int par, int val){  //当前结点 父亲结点 父亲连边的值

    f[now][0]=par; v[now][0]=val; dep[now]=dep[par]+1;

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

        f[now][i]=f[f[now][i-1]][i-1];

        v[now][i]=min(v[now][i-1], v[f[now][i-1]][i-1]);

    }

    for (int i=fir[now]; i; i=e[i].next){

        if (e[i].to==par) continue;

        dfs(e[i].to, now, e[i].v);

    }

}

int n, m, q;

int solve(int x, int y){

    if (dep[x]<dep[y]) swap(x, y); int ans=INF;

    for (int i=16; i>=0; --i)

        if (dep[f[x][i]]>=dep[y]) ans=min(ans, v[x][i]), x=f[x][i];

    for (int i=16; i>=0; --i)

        if (f[x][i]!=f[y][i]) ans=min(ans, min(v[x][i], v[y][i])), x=f[x][i], y=f[y][i];

    if (x!=y) ans=min(ans, min(v[x][0], v[y][0]));  //一定要注意两个点是祖孙关系的情况！

    return ans;

}

int main(){

    scanf("%d%d", &n, &m); int t1, t2, t3;

    for (int i=0; i<m; ++i){

        scanf("%d%d%d", &t1, &t2, &t3);

        e1[i].fr=t1; e1[i].to=t2; e1[i].v=t3;

    }

    sort(e1, e1+m, cmp);

    for (int i=1; i<=n; ++i) fa[i]=i;

    for (int i=0; i<m; ++i){  //直接把边都跑一遍就行了!

        if (find(e1[i].fr)==find(e1[i].to)) continue;

        addedge(e1[i].fr, e1[i].to, e1[i].v);

        addedge(e1[i].to, e1[i].fr, e1[i].v);

        fa[find(e1[i].fr)]=find(e1[i].to);

    }

    for (int i=1; i<=n; ++i) if (fa[i]==i) dfs(i, 0, 0);  //分成许多个子树

    scanf("%d", &q);

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

        scanf("%d%d", &t1, &t2);

        if (find(t1)!=find(t2)){ puts("-1"); continue; }

        printf("%d\n", solve(t1, t2));

    }

    return 0;

}

巴特西

NOIP2013 货车运输（最大生成树，倍增）

NOIP2013 货车运输（最大生成树，倍增）

最新文章

热门文章