威风镰鼬

题解

/ 注册

全部文章 / 题解（共3篇）

题解 | #Desert King#

思路分数规划问题。我们可以求得每两个村子的距离和花费，然后列举最大的ans使得∑（costi−ans∗leni）=0\sum （cost_i-ans*len_i）=0 ∑（costi−ans∗leni）=0 我们固定住1号作为根节点，只需要建一棵最小生成树，二分答案即可求出。（每个点都是与最...

最小生成树 MST 分数规划二分

2021-11-16

1 293

题解 | #[SCOI2005]繁忙的都市#

思路最小生成树的板子题，前置知识：并查集以及Kruskal算法；答案要求输出最小生成树的边数（那肯定是n-1啊）以及最大权值的边（那肯定是最后连的那一条啊）因为做过最小生成树的课件，代码注释解释了很多，大家可以看看。代码 #include<bits/stdc++.h> using n...

最小生成树 Kruskal 并查集

2021-07-29

1 489

题解 | #道路建设#

思路最小生成树板子题，用Kruskal硬过就行了。算法流程：初始设点在集合A，无连边；将图中的边按照权值从小到大排序，然后从最小的边开始连接（使用并查集）；将边的两端点加入集合B，如果当前边的两个端点不都在集合A，则进行连接；选择m-1条边的时候刚好将m个点连上，此时判断权值之和是否大于c。代码...

最小生成树 Kruskal NOIP

2021-06-12

1 430