P1967 货车运输

题目描述

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

说明

对于 100%的数据，0 < 城市数n < 10,000，0 < 道路数m < 50,000，0 < 询问数q< 30,000，0 ≤ 限重z ≤ 100,000。

鉴于这是个稀疏图，我们用kruskal。

最小生成树有一个定理，就是边集中最大的边最小。

那么我们魔改一下kruskal使它变成求最大生成树，就有最小边最大的定理。

之后就可以通过一些手段来处理造出来的生成树了

树链剖分辣么长，懒得打

所以博主这儿用的倍增

f1[i][j]表示i点往上跳2^j距离到达的点

f2[i][j]表示i点往上跳2^j距离的路径上的最小值

就可以暴力求LCA辣啊哈哈哈哈

这里推荐一个更快的大佬code-> http://www.cnblogs.com/xzz_233/p/7614189.html .

代码蒯上

#include<iostream>

#include<iomanip>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

inline int gotcha()

{

    register int _a=0;bool _b=1;register char _c=getchar();

    while(_c<'0' || _c>'9'){if(_c=='-')_b=0;_c=getchar();}

    while(_c>='0' && _c<='9')_a=_a*10+_c-48,_c=getchar();

    return _b?_a:-_a;

}

const int _ = 10002;

using namespace std;

struct edge{int to,ne,len;edge(){to=ne=len=0;}}e[10*_];

struct sav

{

    int fr,to,len;sav(){fr=to=len=0;}

    const bool operator < (const sav &b)const{return len>b.len;}

}tp[5*_];

int he[_],ecnt=0,dep[_],f1[_][18],f2[_][18],n,m,fa[_],gfa[_];

void add(int fr,int to,int len)

{e[++ecnt].to=to,e[ecnt].len=len,e[ecnt].ne=he[fr],he[fr]=ecnt;}

int finder(int a){return gfa[a]!=a?gfa[a]=finder(gfa[a]):a;}

void link(int a,int b){gfa[finder(b)]=finder(a);}

void plant(int a)

{

    for(int i=he[a],j;i;i=e[i].ne)

    {

        j=e[i].to;if(j==fa[a])continue;

        fa[j]=a,f1[j][0]=a,f2[j][0]=e[i].len,dep[j]=dep[a]+1,plant(j);

    }

}

int driver(int st,int ta)

{

    register int i,mi=2e9;

    if(dep[st]>dep[ta])

        for(i=16;i>=0;i--)if(f1[st][i]!=0 && dep[f1[st][i]]>=dep[ta])

            mi=min(mi,f2[st][i]),st=f1[st][i];

    if(dep[ta]>dep[st])

        for(i=16;i>=0;i--)if(f1[ta][i]!=0 && dep[f1[ta][i]]>=dep[st])

            mi=min(mi,f2[ta][i]),ta=f1[ta][i];

    if(st==ta)return mi;

    for(i=16;i>=0;i--)if(f1[st][i]!=f1[ta][i])

        mi=min(mi,min(f2[st][i],f2[ta][i])),st=f1[st][i],ta=f1[ta][i];

    return min(mi,min(f2[st][0],f2[ta][0]));

}

int main()

{

    register int i,j,k;

    n=gotcha(),m=gotcha();

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

    for(i=1;i<=m;i++)tp[i].fr=gotcha(),tp[i].to=gotcha(),tp[i].len=gotcha();

    sort(tp+1,tp+m+1);

    for(i=1;i<=m;i++)

        if(finder(tp[i].fr)!=finder(tp[i].to))

        {

            link(tp[i].fr,tp[i].to);

            add(tp[i].fr,tp[i].to,tp[i].len),add(tp[i].to,tp[i].fr,tp[i].len);

        }

    for(i=1;i<=n;i++)if(i==gfa[i])fa[i]=i,dep[i]=1,plant(i);

    for(i=1;i<=16;i++)

        for(j=1;j<=n;j++)

        {

            f1[j][i]=f1[f1[j][i-1]][i-1];

            f2[j][i]=min(f2[j][i-1],f2[f1[j][i-1]][i-1]);

        }

    i=gotcha();

    while(i--)

    {

        j=gotcha(),k=gotcha();

        printf("%d\n",(finder(j)==finder(k)?driver(j,k):-1));

    }

    return 0;

}

巴特西

kruskal - 倍增 - 并查集 - Luogu 1967 货车运输

P1967 货车运输

题目描述

说明

最新文章

热门文章