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