noip模拟赛 仓库
2024-10-20 00:52:00
分析:非常像货车运输那道题.先求一下最大生成树.求完之后会发现并不好处理.通常这类求生成树的题目不会就分析kruscal算法的性质.每往最大生成树中加一条边,如果配重大于这条边权,那么这条边所连的两个集合就都要建一个仓库.也可以这么想:本来在所有点都建仓库,如果配重小于这条边的边权,那么少建一个仓库.把所有的边权放进一个数组里,排个序,二分一下就好了.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; int n,m,q,fa[],p[],cnt;
struct node
{
int u,v,w;
}e[]; bool cmp(node a,node b)
{
return a.w > b.w;
} int find(int x)
{
if (x == fa[x])
return x;
return fa[x] = find(fa[x]);
} bool cmp2(int x,int y)
{
return x > y;
} int main()
{
scanf("%d%d%d",&n,&m,&q);
for (int i = ; i <= n; i++)
fa[i] = i;
for (int i = ; i <= m; i++)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
sort(e + ,e + + m,cmp);
for (int i = ; i <= m; i++)
{
int fu = find(e[i].u),fv = find(e[i].v);
if (fu != fv)
{
fa[fu] = fv;
p[++cnt] = e[i].w;
}
}
sort(p + ,p + + cnt,cmp2);
while (q--)
{
int temp;
scanf("%d",&temp);
int l = ,r = cnt,ans = ;
while (l <= r)
{
int mid = (l + r) >> ;
if (p[mid] >= temp)
{
ans = mid;
l = mid + ;
}
else
r = mid - ;
}
printf("%d\n",n - ans);
} return ;
}
最新文章
- UEditor演变的迷你版编辑器
- ASP.NET MVC运行机制源码剖析
- Beta版本冲刺第六天 12.12
- [转载]有了 malloc/free 为什么还要 new/delete ?
- 迅影QQ视频查看v2.0 源码
- semantic versioning语义化版本号
- 用 oracle vitual box 克隆虚拟机,找不到eth0的解决方案
- ENVISAT卫星及ASAR数据介绍
- FileOutputStream flush()
- 【Xilinx-VDMA模块学习】-00-开始
- JetBrains套装免费学生授权申请(IntelliJ, WebStorm...)
- Apache shiro集群实现 (四)shiro授权(Authentication)--访问控制
- 在 root 下执行 Oracle 程序时找不到 libclntsh.so.11.1 错误的解决办法。
- QLineEdit拾遗:数据的过滤、验证和补全
- 在SuperMap iDesktop中如何快速追加记录行?
- linux环境下安装tcping工具测试访问超时
- C# 语言历史版本特性(C# 1.0到C# 7.1汇总更新)
- 【索引失效】什么情况下会引起MySQL索引失效
- Ubuntu 下安装Go语言
- Ext.NET Ext.JS 常用代码片段摘录