HDU 3938
2024-09-02 16:44:04
并查集的离线算法。
题意是大坑。理解为寻找两点之间所有路径中的最长的边的值小于输入的值的点对的个数。
直接来代码。
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct ab
{
int a,b,c;
};
int n;
struct ab poi[];
struct cd
{
int id,num,cc;
};
struct cd li[];
int me[];
int numb[];
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=;i<=n;i++)
{
me[i]=i;
numb[i]=;
}
for(i=;i<m;i++)
{
scanf("%d%d%d",&poi[i].a,&poi[i].b,&poi[i].c);
}
sort(poi,poi+m,cmp1);
for(i=;i<q;i++)
{
scanf("%d",&li[i].id);
li[i].num=i;
}
sort(li,li+q,cmp2);
j=;
ans=;
for(i=;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=;i<q;i++)
{
printf("%d\n",li[i].cc);
}
}
return ;
}
最新文章
- html5的新特性——拖放API
- 对java多线程的认识
- vmware 无法打开内核设备 \\.\Global\vmx86: 系统找不到指定的文件
- IOS的浅拷贝和深拷贝
- iOS开发--隐藏(去除)导航栏底部横线
- Resources in Visual Tracking(转载)
- scala言语基础学习五
- UVa 540 Team Queue 【STL】
- Nagios3完整配置文档
- 展讯CEO:低毛利生存 由中低端转向高端
- vb combobox 用法问题总结
- .net图片自动裁剪白边函数案例
- Testlink1.9.14介绍及使用
- messages exchanged between the client&#39;s and server&#39;s computers will never be lost, damaged, or received out of order. [1]
- [BZOJ 4417][Shoi2013]超级跳马
- PYQT5登录界面跳转主界面方法
- [Postman]捕获HTTP请求(14)
- 关于 tensorflow-gpu 中 CUDA 和 CuDNN 版本适配问题
- RPC框架研究(二)Hadoop源代码-1
- sqlserver数据库使用空间监控