BZOJ 3732 Network

NOIP2013货车运输。

注意算dis的时候不按边权。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxv 15050
#define maxe 600500
using namespace std;
struct regis
{
    int u,v,w;
}r[maxe];
struct edge
{
    int v,w,nxt;
}e[maxe];
int n,m,k,g[maxv],x,y,z,nume=0,father[maxv];
int anc[maxv][20],mx[maxv][20],dis[maxv];
bool cmp(regis x,regis y)
{
    return x.w<y.w;
}
int getfather(int x)
{
    if (x!=father[x]) 
        father[x]=getfather(father[x]);
    return father[x];
}
void addedge(int u,int v,int w)
{
    e[++nume].v=v;
    e[nume].w=w;
    e[nume].nxt=g[u];
    g[u]=nume;
}
void kruskal()
{
    sort(r+1,r+m+1,cmp);
    for (int i=1;i<=m;i++)
    {
        int u=r[i].u,v=r[i].v,w=r[i].w;
        int f1=getfather(u),f2=getfather(v);
        if (f1!=f2)
        {
            addedge(u,v,w);
            addedge(v,u,w);
            father[f1]=f2;
        }
    }
}
void dfs(int x,int father)
{
    anc[x][0]=father;
    for (int i=g[x];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if (v!=father)
        {
            mx[v][0]=e[i].w;
            dis[v]=dis[x]+1;
            dfs(v,x);
        }
    }
}
int lca(int x,int y)
{
    if (dis[x]>dis[y]) swap(x,y);
    for (int i=19;i>=0;i--)
    {
        if ((dis[anc[y][i]]>=dis[x]) && (anc[y][i]!=0))
            y=anc[y][i];
    }
    for (int i=19;i>=0;i--)
    {
        if (anc[x][i]!=anc[y][i])
        {
            x=anc[x][i];
            y=anc[y][i];
        }
    }
    if (x==y) return x;
    else return anc[x][0];
}
void work()
{
    scanf("%d%d",&x,&y); 
    int r=lca(x,y),maxnum=0;
    if (x!=r)
    {
        for (int i=19;i>=0;i--)
        {
            if ((dis[anc[x][i]]>=dis[r]) && (anc[x][i]!=0))
            {
                maxnum=max(maxnum,mx[x][i]);
                x=anc[x][i];
            }
        }
    }
    if (y!=r)
    {
        for (int i=19;i>=0;i--)
        {
            if ((dis[anc[y][i]]>=dis[r]) && (anc[y][i]!=0))
            {
                maxnum=max(maxnum,mx[y][i]);
                y=anc[y][i];
            }
        }
    }
    printf("%d
",maxnum);
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=m;i++)
        scanf("%d%d%d",&r[i].u,&r[i].v,&r[i].w);
    for (int i=1;i<=n;i++) father[i]=i;
    kruskal();
    dfs(1,0);
    for (int e=1;e<=19;e++)
        for (int i=1;i<=n;i++)
        {
            anc[i][e]=anc[anc[i][e-1]][e-1];
            mx[i][e]=max(mx[i][e-1],mx[anc[i][e-1]][e-1]);
        }
    for (int i=1;i<=k;i++)
        work();
    return 0;
}