HDU 3938

セットのオフラインアルゴリズムを調べます.
題意は大きな穴だ.2点間のすべてのパスの中で最も長いエッジを探す値は、入力した値の点対の数より小さいと理解されます.
直接コードが来ます.

#include<stdio.h>

#include<iostream>

#include<algorithm>

using namespace std;

struct ab

{

    int a,b,c;

};

int n;

struct ab poi[50050];

struct cd

{

    int id,num,cc;

};

struct cd li[50050];

int me[50050];

int numb[50050];

bool cmp1(struct ab a,struct ab b)

{

    return a.c<b.c;

}

bool cmp2(struct cd a,struct cd b)

{

    return a.id<b.id;

}

bool cmp3(struct cd a,struct cd b)

{

    return a.num<b.num;

}

void link(int a,int b)

{

    me[b]=a;

    numb[a]+=numb[b];

}

int findme(int a)

{

    if(a!=me[a])

        return me[a]=findme(me[a]);

    return me[a];

}

int main()

{

    int m,q,i,j,k,ans,tmpa,tmpb;

    while(scanf("%d%d%d",&n,&m,&q)!=EOF)

    {

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

        {

            me[i]=i;

            numb[i]=1;

        }

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

        {

            scanf("%d%d%d",&poi[i].a,&poi[i].b,&poi[i].c);

        }

        sort(poi,poi+m,cmp1);

        for(i=0;i<q;i++)

        {

            scanf("%d",&li[i].id);

            li[i].num=i;

        }

        sort(li,li+q,cmp2);

        j=0;

        ans=0;

        for(i=0;i<q;i++)

        {

            for(;j<m;j++)

            {

                if(poi[j].c>li[i].id)

                {

                    break;

                }

                else

                {

                    tmpa=findme(poi[j].a);

                    tmpb=findme(poi[j].b);

                    if(tmpa!=tmpb)

                    {

                        ans+=numb[tmpa]*numb[tmpb];

                        link(tmpa,tmpb);

                    }

                }

            }

            li[i].cc=ans;

        }

        sort(li,li+q,cmp3);

        for(i=0;i<q;i++)

        {

            printf("%d
",li[i].cc);

        }

    }

    return 0;

}