2018.07.22 洛谷P1967 货车运输（kruskal重构树）

传送门

这道题以前只会树剖和最小生成树+倍增。

而现在学习了一个叫做kruskal" role="presentation" style="position: relative;">kruskalkruskal重构树的优美姿势，搞得我不想写都不行了。

好吧事实上krsukal" role="presentation" style="position: relative;">krsukalkrsukal重构树上两点的lca" role="presentation" style="position: relative;">lcalca就是它们路径上的瓶颈这个优美的性质可以秒杀这道题。

代码如下：

#include<bits/stdc++.h>
#define N 10005
#define M 50005
using namespace std;
inline int read(){
    int ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans;
}
inline void write(int x){
    if(x>0)write(x/10);
    putchar((x%10)^48);
}
int n,m,q,fa[N<<1],son[N<<1][2],w[N<<1],pa[N<<1][20],dep[N<<1];
bool vis[N<<1];
inline int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}
struct Node{int u,v,w;}e[M];
inline bool cmp(Node a,Node b){return a.w>b.w;}
inline void dfs(int p){
    for(int i=1;i<=19;++i)pa[p][i]=pa[pa[p][i-1]][i-1];
    vis[p]=true;
    if(!son[p][0]&&!son[p][1])return;
    dep[son[p][0]]=dep[son[p][1]]=dep[p]+1;
    dfs(son[p][0]),dfs(son[p][1]);
}
inline void kruskal(){
    sort(e+1,e+m+1,cmp);
    int cnt=n;
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=(n<<1);++i)fa[i]=i;
    for(int i=1;i<=m;++i){
        int x=find(e[i].u),y=find(e[i].v);
        if(x!=y){
            pa[x][0]=pa[y][0]=fa[x]=fa[y]=++cnt;
            son[cnt][0]=x,son[cnt][1]=y;
            w[cnt]=e[i].w;
        }
    }
    for(int i=cnt;i>=1;--i)if(!vis[i])dfs(i);
}
inline int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=19;i>=0;--i){
        if(dep[pa[x][i]]>=dep[y])x=pa[x][i];
        if(x==y)return x;
    }
    for(int i=19;i>=0;--i)if(pa[x][i]!=pa[y][i])x=pa[x][i],y=pa[y][i];
    return pa[x][0];
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=m;++i)e[i].u=read(),e[i].v=read(),e[i].w=read();
    kruskal();
    q=read();
    while(q--){
        int u=read(),v=read(),x=find(u),y=find(v);
        if(x!=y){puts("-1");continue;}
        printf("%d\n",w[lca(u,v)]);
    }
    return 0;
}

巴特西

2018.07.22 洛谷P1967 货车运输（kruskal重构树）

最新文章

热门文章