【Tree】

【Tree】

【题目描述】 给你一堆边,其中有些边为黑色,有些边为白色,每条边有一条边权。 这些边一定能构造成一颗树,请问其中恰好选K条白边的最小生成树的权值和是多少? 【输入格式】 第一行三个整数n m k表示点数,边数,以及K 接下来m行每行四个整数u v w c表示u到c有一条权值为w颜色为c(0为白色1为黑色)的边(双向边) 【输出格式】 一行一个整数,表示恰好选...
【Highways】

【Highways】

题目描述 Wisekingdom 有 N 座城市,为了使 wisekingdom 的交通更加便利,国王决定修建高速公路,使得每两个城市之间都有高速公路相通。现在国王想知道的并不是修建的高速路的最小长度和。他感兴趣的是所建高速公路中最长的一条的长度,他希望这个最长长度尽量小。 输入格式 第一行:一个正整数 N ,  N<=500; 接下来 N 行,...
【Minimum】

【Minimum】

【问题描述】 给出一幅由n个点m条边构成的无向带权图。 其中有些点是黑点,另外点是白点。 现在每个白点都要与它距离最近的黑点通过一些边连接(就是最短路)(如果有很多歌,可以选取其中任意一个。),我们想要使得花费的代价最小。请问这个最小代价是多少? 【输入格式】 第一行两个整数n,m; 第二行n个整数,0表示白点,1表示黑点 接下来m行,每行三个整数x y z...
【连通块】

【连通块】

题目描述 一个点每过一个单位时间就会向 4 个方向扩散一个距离,如下图所示: (一个点每过一个单位时间向四个方向扩散一个距离) 两个点 a、b 连通,记作 e(a,b),当且仅当 a、b 的扩散区域有公共部分。连通块的定义是块内的任意两点 u、v 都必定存在路径 e(u,a0),e(a0,a1),…,e(ak,v)。 给定平面上的 n 个点,问最早什...