题目地址：HDU 3635 加权并查集水题。 用num数组维护该城市有多少龙珠，用times数组维护每个龙珠运输了多少次。num数组在合并的时候维护。times数组由于每个都不一样，所以要在找根的时候递归来全部维护。 最终，x龙珠所在的城市就是x节点所在的根，x结点所在的跟的num数组值是该城市的龙珠数。times[x]为该龙珠运输了多少次。 代码如下： #include <iost

题目连接：3635 - Pie 题目大意： 有m个派， 要分给n + 1个人， 要求每个人拿到的大小相同， 并且每个人的派必须是一整块， 不能说分别从两个派切出一块凑成。 现在给出m个派的半径(派均为圆柱，高为1），输出每人可以拿到的最大派的体积。 解题思路：二分查找。 #include <stdio.h>#include <string.h>#include <m

题干： 大意是f+1个人来分n个圆形派（每个的大小不一定相同）。每个人必须分得一整块，而且每个人分得的面积相同。求每个人分得的最大面积是多少。 分析： 看了看书上的分析，就是采用二分法，查找到合适的面积x，使得问题转化为“能否可以让每人得到一块x的派”。 代码： #include <string.h>#include <iostream>#include <algorithm>

HDU - 3635 Dragon Balls 1.题面 传送门 2.解题思路 要求给出在一个并查集的元素中，每个元素在哪个集合中，该元素所在的集合中有几个元素，该元素参与了几次合并操作。我的并查集自然支持前两个操作。后一个操作实际上询问的是在一个并查集中某个元素到祖先的距离是多少。某个节点的移动次数等于自己父亲节点的移动次数+1，可以使用和记录集合个数一样的方法来记录。这里用的是暴力

题意：给出一张图，n<=1000,m<=10000.  有一辆车想从图的一个地方到达另外一个地方，每个点是一个卖油的地方，每个地方买的有价格不一样，车的最大装油量是c，求初始点到终止点的最小花费。 网上大部分的思路都是类似于dij的那种扩展。 首先定义一个二维数组dp。 dp[i][j] 表示走到i点剩余j个单位的汽油时的最小花费 然后维护一个优先队列。  每次有两种可扩展的状态，一是

一开始想用DP做的，后来想了想，用DP的肯定会超时。 然后想用dij跑图就可以了，然后再加上优先队列优化。 没到达一个点的时候，有两种选择，一种是一点油都不加，然后往后跑。 另外一种就是加一升的油。 用优先队列选择最优的子结果。 #include<iostream>#include<algorithm>#include<stdio.h>#include<string.h>#i