TIOJ 1213 樹論 之 最遠距點對

[DFS]

將所有的邊存在一個陣列

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define MAX 100000
#define max(a,b) ((a)>(b)) ? (a) : (b)
struct adj
{
    int a;int b;
    int w;
} adjs[2*MAX+1];
int corp[MAX+1];
int diam=0;
int compare(const void *a, const void *b)
{
    struct adj c = *(struct adj *)a;
    struct adj d = *(struct adj *)b;
    if(c.a < d.a) {return -1;}
    else if (c.a == d.a)
    {
        if(c.b>d.b)
            return 1;
        else
            return 0;
    }
    else
        return 1;
}
int bs(int down,int up,int f)
{
    if(down==up)
    {
        if(adjs[down].a==f)
            return down;
        return -1;
    }
    if(down==up-1)
    {
        if(adjs[down].a==f)
            return down;
        else if(adjs[up].a==f)
            return up;
        else
            return -1;
    }
    int mid=(up+down)/2;
    if(adjs[mid].a>=f)
        return bs(down,mid,f);
    else
        return bs(mid,up,f);
}
bool check(int a,int b)
{
    if(corp[a]==-1)
        return false;
    for(int lx=corp[a];adjs[lx].a==a;lx++)
        if(adjs[lx].b==b)
            return true;
    return false;
}
int dfs(int px,int x)
{

    int h1,h2;
    h1=h2=0;
    for(int lx=0;adjs[corp[x]+lx].a==x;lx++)
    {
        int nx=adjs[corp[x]+lx].b;
        if(nx==px) continue;
        int h=dfs(x,nx)+adjs[corp[x]+lx].w;
        if(h>h1){h2=h1;h1=h;}
        else if(h>h2)h2=h;
    }
    diam=max(diam,h1+h2);
    return h1;
}
int main()
{
    int n;
    while(scanf("%d",&n)&&n)
    {
        int a,b,w,adjcnt;
        adjcnt=0;
        diam=0;
        for(int ln=1;ln<n;ln++)
        {
            scanf("%d %d %d",&a,&b,&w);
            adjs[adjcnt++].a=a;
            adjs[adjcnt-1].b=b;
            adjs[adjcnt-1].w=w;
            adjs[adjcnt++].a=b;
            adjs[adjcnt-1].b=a;
            adjs[adjcnt-1].w=w;
        }
        qsort((void *)adjs, adjcnt, sizeof(adj), compare);
        
        memset(corp,-1,sizeof(corp));
        for(int lx=0;lx<adjcnt;lx++)
            if(corp[adjs[lx].a]<0)
                corp[adjs[lx].a]=lx;
        dfs(adjs[0].a,adjs[0].a);
        printf("%d\n",diam);
    }

    return 0;
}