http://acm.hdu.edu.cn/showproblem.php?pid=5441
题目大意是给一个n个城市(点)m条路线(边)的双向的路线图,每条路线有时间值(带权图),然后q个询问,每个询问一个时间值
求不大于这个时间的可以连通的城市有多少种连法
比如样例中第一个询问6000,不大于6000时间值的连通城市有3,5.所以有3-->5,5-->3两种
第二个询问10000,符合条件的连通的城市有2,3,5,所以有2-->3,3-->2,2-->5,5-->2,3-->5,5-->3六种
利用结构体储存点与权值然后把权值排序,找出符合条件的城市点,利用并查集记录相连的点然后合并,整合路线
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int father[],num[];
int a[];
void lsy(int n)
{
for (int i=;i<=n;i++)
{
father[i]=i;
num[i]=;
}
}
struct point {
int x,y,z;
bool operator <(const point& q)const
{
return z<q.z;
}
};
point yj[];
struct node {
int w,id;
bool operator <(const node &q)const
{
return w<q.w;
}
};
node yjj[];
int _find(int x)
{
if (father[x]==x)return x;
father[x]=_find(father[x]);
return father[x];
}
int main()
{
int t,n,m,q,i;
while (~scanf("%d",&t))
{
while (t--)
{
scanf("%d %d %d",&n,&m,&q);
memset(a,,sizeof(a));
for (i=;i<=m;i++)
scanf("%d %d %d",&yj[i].x,&yj[i].y,&yj[i].z);
sort(yj+,yj+m+);
lsy(n);
for (i=;i<=q;i++)
{
scanf("%d",&yjj[i].w);
yjj[i].id=i;
}
sort(yjj+,yjj+q+);
int ans=,j=;
for (i =;i<=q;i++)
{
while (j<=m&&yj[j].z<=yjj[i].w )
{
int sx=_find(yj[j].x);
int sy=_find(yj[j].y);
j++;
if (sx==sy) continue;
ans+=(num[sx]+num[sy])*(num[sx]+num[sy]-)-num[sx]*(num[sx]-) - num[sy]*(num[sy]-);//合并之后的关系
father[sx]=sy;
num[sy]+=num[sx];
}
a[yjj[i].id]=ans;
}
for (i=;i<=q;i++)
printf("%d\n",a[i]);
}
}
return ;
}