分析:非常像货车运输那道题.先求一下最大生成树.求完之后会发现并不好处理.通常这类求生成树的题目不会就分析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 ;
}

最新文章

  1. UEditor演变的迷你版编辑器
  2. ASP.NET MVC运行机制源码剖析
  3. Beta版本冲刺第六天 12.12
  4. [转载]有了 malloc/free 为什么还要 new/delete ?
  5. 迅影QQ视频查看v2.0 源码
  6. semantic versioning语义化版本号
  7. 用 oracle vitual box 克隆虚拟机,找不到eth0的解决方案
  8. ENVISAT卫星及ASAR数据介绍
  9. FileOutputStream flush()
  10. 【Xilinx-VDMA模块学习】-00-开始
  11. JetBrains套装免费学生授权申请(IntelliJ, WebStorm...)
  12. Apache shiro集群实现 (四)shiro授权(Authentication)--访问控制
  13. 在 root 下执行 Oracle 程序时找不到 libclntsh.so.11.1 错误的解决办法。
  14. QLineEdit拾遗:数据的过滤、验证和补全
  15. 在SuperMap iDesktop中如何快速追加记录行?
  16. linux环境下安装tcping工具测试访问超时
  17. C# 语言历史版本特性(C# 1.0到C# 7.1汇总更新)
  18. 【索引失效】什么情况下会引起MySQL索引失效
  19. Ubuntu 下安装Go语言
  20. Ext.NET Ext.JS 常用代码片段摘录

热门文章

  1. Android Dialogs(4)Dialog事件处理
  2. Styles and Themens(3)android所有主题表
  3. Codeforces Round #179 (Div. 1)
  4. h5学习-webstorm工具的激活
  5. ReactJS-0-React介绍
  6. iOS Programming Web Services and UIWebView
  7. 黑马程序员----java基础:异常
  8. -webkit/IE/Firefox的一些样式
  9. Python 保留n位小数
  10. MySQL索引的用处