火车运输[NOIP 2013 提高组 Day 1]

https://vijos.org/p/1843

本题 kruskal+倍增lca

WA了三次 T_T

总结出一些注意事项：

1. 一定要想明白每一部分是求最大值还是最小值！！！（WA 1）

2. 注意操作顺序，别把要用的变量的数值改没！！！（WA 2）

3. 仔细看题，如本题让“”货车不能到达目的地，输出-1“”，而货车载重为零则应输出0！！！！！！（WA 3）

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
struct edg
{
    int x;
    int y;
    int z;
}edge[];
int n,m;
int q;
bool cmp(edg a,edg b)
{
    return a.z>b.z;
}
int min(int a,int b){return a<b?a:b;}
int father[];
int find(int a)
{
    if(father[a]!=a) father[a]=find(father[a]);
    return father[a];
}
void unionn(int a,int b)
{
    father[a]=b;
}
int to[],val[],nextt[],head[],cnt;
void add(int a,int b,int c){to[++cnt]=b;val[cnt]=c;nextt[cnt]=head[a];head[a]=cnt;}
int fa[][];
int minn[][];
int deep[];
void add_root()
{
    int v[];
    memset(v,,sizeof(v));
    for(int i=;i<=n;i++)
    {
        int a=find(i);
        if(!v[a])
        {
            add(n+,a,);
            add(a,n+,);
            v[a]=;
        }

    }
}
int visited[];
void dfs(int pos,int pre,int step,int vv)
{
    visited[pos]=;
    fa[pos][]=pre;deep[pos]=step;
    minn[pos][]=vv;
    for(int i=head[pos];i;i=nextt[i])
    {
        if(!visited[to[i]])
        {
            dfs(to[i],pos,step+,val[i]);
        }
    }
}
void swap(int &a,int &b){int t=a;a=b;b=t;}
int lca_min(int x,int y)
{
    int re;
    int ans=;
    if(deep[x]<deep[y])swap(x,y);
    for(int i=;i>=;i--)
    {
        if(deep[fa[x][i]]>=deep[y])
        {
            ans=min(ans,minn[x][i]);
            x=fa[x][i];
        }
    }
    if(x==y) return ans;
    for(int i=;i>=;i--)
    {
        if(fa[x][i]!=fa[y][i])
        {
            ans=min(ans,minn[x][i]);
            ans=min(ans,minn[y][i]);
            x=fa[x][i];
            y=fa[y][i];
        }
        else
        {
            re=fa[x][i];
        }
    }
    ans=min(ans,minn[x][]);
    ans=min(ans,minn[y][]);
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=;i<=m;i++)
    {
        scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
        edge[i].z++;
    }
    sort(edge+,edge+m+,cmp);
    for(int i=;i<=n;i++) father[i]=i;
    for(int i=;i<=m;i++)
    {
        int a=edge[i].x;
        int b=edge[i].y;
        a=find(a);
        b=find(b);
        if(a!=b)
        {
            unionn(a,b);
            add(edge[i].x,edge[i].y,edge[i].z);
            add(edge[i].y,edge[i].x,edge[i].z);
        }
    }
    memset(minn,,sizeof(minn));
    add_root();
    dfs(n+,n+,,);
    for(int j=;j<=;j++)
    {
        for(int i=;i<=n;i++)
        {
            fa[i][j]=fa[fa[i][j-]][j-];
            minn[i][j]=min(minn[i][j-],minn[fa[i][j-]][j-]);
        }
    }
    scanf("%d",&q);
    for(int i=;i<=q;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        int ans=lca_min(a,b);
        if(ans==) printf("-1\n");
        else printf("%d\n",ans-);
    }
    return ;
}
           

附上几组数据：

/*


5 8
5 4 1
4 2 3
5 3 4
3 1 6
5 1 6
4 2 0
4 2 0
1 2 9
5
1 5
4 3
1 4
4 1
3 4

*/

/*

5 5
2 5 3
5 3 0
1 2 9
3 2 0
4 2 8
5
3 2
2 1
3 4
5 2
1 2


*/

/*

6 8
5 3 7
3 2 3
6 5 2
2 3 6
1 3 6
4 1 3
2 6 9
4 1 1
1
6 4

*/