题意: 在平面上有n个点,要让所有n个点都连通,所以你要构造一些边来连通他们,连通的费用等于两个端点的欧几里得距离的平方.另外还有q个套餐,可以购买,如果你购买了第i个套餐,该套餐中的所有结点将变得相互连通,第i个套餐的花费为ci.求最小花费. 思路: 在这里我们可以采取枚举所有可能 + K算法来得出答案,比如这里有三个套餐,我们利用二进制枚举 001.010.011 .100. 101. 110. 111 分别代表第一个和第二个不要,要第三个(001):不要第一个和第三个,要第二个(010).

[题意] 平面上有\(n(n<=1000)\)个点,你的任务是让所有n个点联通.为此,你可以新建一些边,费用等于两个端点的欧几里得距离平方.另外还有\(q(q<=8)\)个套餐可以购买,如果你购买了第\(i\)个套餐,该套餐中的所有结点将变得相互连接.第\(i\)个套餐的花费为\(C_i\). [算法] \(Kruskal\) [分析] 最容易想到的算法是:先枚举购买哪些套餐,把套餐中包含的权值设为\(0\),然后求最小生成树.由于枚举量为\(O(2^q)\),给边排序的时间复杂度为\(O(n

题意:n家旅店,每个旅店都有坐标x,y,每晚价钱z,m个客人,坐标x,y,钱c,问你每个客人最近且能住进去(非花最少钱)的旅店,一样近的选排名靠前的. 思路:KD树模板题 代码: #include<set> #include<map> #include<stack> #include<cmath> #include<queue> #include<vector> #include<cstdio> #include<c

这个东西代码我是对着Trinkle的写的,所以就不放代码了.. Delaunay剖分的定义: 一个三角剖分是Delaunay的当且仅当其中的每个三角形的外接圆内部(不包括边界)都没有点. 它的存在性是调整法可证的. 最小生成树的性质: 对于每个环c,它上面最长的边一定有一条不在MST上. Delaunay剖分的性质: 如果有一条边的两个端点在一个内部(包括边界)没有其他点的圆上,那么这条边一定在Delaunay剖分内(反证). 那么如果有一条边u,v不在一个Delaunay剖分上,那么在任何一个

题意:平面上有n个点(1<=N<=1000),你的任务是让所有n个点连通,为此, 你可以新建一些边,费用等于两个端点的欧几里得距离的平方.另外还有q(0<=q<=8)个套餐(数量小,可枚举),可以购买,如果你购买了第i个套餐,该套餐 中的所有结点将变得相互连通,第i个套餐的花费为ci. 分析:按照刘汝佳的思路做的.首先求一次本身的最小生成树值,然后枚举购买的套餐(二进制枚举),每次购买了之后,将其权值设为0,并且加进最小生成树. #include<cstdio> #in

题意:平面上有n个点(1<=N<=1000),你的任务是让所有n个点连通,为此,你可以新建一些边,费用等于两个端点的欧几里得距离的平方.另外还有q(0<=q<=8)个套餐,可以购买,如果你购买了第i个套餐,该套餐中的所有结点将变得相互连通,第i个套餐的花费为ci. kruskal: 先求一次原图的最小生成树,得到n-1条边,然后每次枚举完套餐后只考虑套餐中的边和这n-1条边,则枚举套餐之后再求最小生成树. key: kruskal算法中,那些两端已经属于同一个连通分量的边不会再加到

题意: 要使n个点之间能够互通,要使两点直接互通需要耗费它们之间的欧几里得距离的平方大小的花费,这说明每两个点都可以使其互通.接着有q个套餐可以选,一旦选了这些套餐,他们所包含的点自动就连起来了,所需要做的就是连上还未通的即可,q<=8.可以多买.求最小生成树所需的代价. 思路: 与普通求MST不同的就是多了套餐,而且还可以多买.每个套餐有买或不买两种可能,那么有28种可能,即256种. 如果不买套餐,至少需要求1次MST是确定的,这个复杂度已经是O(n*n)了.还得考虑哪些餐套可以搭配来买更便

[题意] 平面上有n个点(1<=N<=1000),你的任务是让所有n个点连通,为此,你可以新建一些边,费用等于两个端点的欧几里得距离的平方. 另外还有q(0<=q<=8)个套餐,可以购买,如果你购买了第i个套餐,该套餐中的所有结点将变得相互连通,第i个套餐的花费为ci. 求最小花费. Input (1 ≤ n ≤ 1000)  (0 ≤ q ≤ 8). The second integer is the the cost of the subnetwork(not greater

Description 平面上有n个点(1<=N<=1000),你的任务是让所有n个点连通,为此,你可以新建一些边,费用等于两个端点的欧几里得距离的平方. 另外还有q(0<=q<=8)个套餐,可以购买,如果你购买了第i个套餐,该套餐中的所有结点将变得相互连通,第i个套餐的花费为ci. 求最小花费. Solution 对于套餐可以用子集枚举处理,求最小生成树时只需考虑原图是最小生成树中的边. 正确性可以按Kruskal过程,以前被舍弃的边选了套餐后依然会被舍弃. Code #incl

题意:给出n个点的坐标,现在需要让这n个点连通,可以直接在点与点之间连边,花费为两点之间欧几里得距离的平方,也可以选购套餐,套餐中所含的点是相互连通的 问最少的花费 首先想kruskal算法中,被加入的边已经是最优的了,所以当选择完套餐后,之前被丢弃的边也不会再进入最小生成树 然后就可以先求一次原图的最小生成树,保存下进入最小生成树的n-1条边 再枚举选择的套餐的情况,再求最小生成树,这里用的二进制法枚举 最后维护一个最小值就可以了 思路虽然看懂了,可是代码根本就写不出来,看着标程写的,最后还是

迷之节约 Time Limit: 1000ms Memory limit: 65536K 有疑问?点这里^_^ 题目描述 FF超级有钱,最近又买了n个(1 <= n <= 300)小岛,为了能在岛之间游玩,FF决定要在岛之间修桥以保证任意两岛之间都要可达.但是FF又超级抠门,想让造桥费用最小.现在由于技术原因,一座桥的造价为两桥之间直线距离的平方.现在给你桥的坐标,让你求最小造价是多少. 输入 多组输入. 对于每组数据,第一行输入n,接下来的n行,每行两个整数x,y(-1000 <= x

两个BUG鸣翠柳,一行代码上西天... hdu4786 Fibonacci Tree(生成树)问能否用白边和黑边构成一棵生成树,并且白边数量是斐波那契数. 题解:分别优先加入白边和黑边,求出生成树能包含白边的最大值和最小值,其间有值为斐波那契数即可. #include<cstdio> #include<cstring> #include<algorithm> using namespace std; ; ; struct edge{ int u,v,w; }e[M];

先求一次最小生成树,可以排除n*(n*1)/2-(n-1)条边,每次利用二进制法枚举套餐的选择,套餐中的点直接处理,如果两个套餐有公共点直接合并,他们一定连通,然后枚举第一步最小生成树得到的n-1条边就能够得到在购买当前套餐下能得到的最优解. 注意:修建两点之间的道路的费用是欧几里德距离的平方. AC代码: #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using

题意:给定n个点,你的任务是让它们都连通.你可以新建一些边,费用等于两点距离的平方(当然越小越好),另外还有几种“套餐”,可以购买,你购买的话,那么有些边就可以连接起来, 每个“套餐”,也是要花费的,让你求出最少花费. 析:首先想到的是把所有情况都考虑算一下,然后找出最少的,先算没有“套餐”的,然后算有的,用二进制枚举的话,总时间复杂度为O(2qn2+n2logn),这个时间复杂度太大了吧,肯定会超时, 那么我们就可以优化一下,首先先算出来最小生成树,并且把每条边都保存下来,那么加了“套餐”之后

链接: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3592 题意: 平面上有n个点(1≤n≤1000),你的任务是让所有n个点连通.为此,你可以新建一些边,费用等于两个端点的欧几里德距离的平方.另外还有q(0≤q≤8)个“套餐”可以购买,如果你购买了第i个套餐,该套餐中的所有结点将变得相互连通.第i个套餐的花费为Ci.求最小的花费.

题意: 秦始皇修路,已知n个城市的坐标以及该城市的人口数,修路的费用是两个城市之间的欧几里得距离,其中可以有一条路不用花费代价但是要求这条路连接的两个城市的人口之和A/B尽量大,其中B是修路的总费用. 输入t组数据 输入n城市个数 输入n行x,y,z表示坐标和人口数 输出A/B. 代码: //类似次小生成树的处理方法,先求出最小生成树值ans,枚举要选的边u-v,ans减去u-v路径中的最大权值之后比较比值大小. #include<iostream> #include<cstdio>

https://vjudge.net/problem/UVA-1151 题意,给出N个点以及二维坐标,可以在任意两点间建立通路,代价是两点欧几里得距离的平方,同时有q个套餐,套餐x有qx个点,代价是qw, 花费qw就能将这qx个点全部相联通,套餐可以任意选择几种或不选,求将所有的点联通所要的最小代价. 很容易想到一个暴力做法,遍历2^q种套餐方案,将这些点提前加入后再跑kruskal,这样的复杂度有些高了. 其实简单证明一下,我们可以先不买套餐跑一遍kruskal,之后保存下来所选的边. 遍历所

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1626 题意: 有n个农场,坐标为(x[i],y[i]). 有m条原先就修好的路,连接农场(a[i],b[i]). 现在要修一些路(首尾连接两个农场,长度为欧几里得距离),使得所有农场互相连通. 问修路的最短总距离. 题解: 最小生成树. 提前将m对点合并,再求最小生成树. 注:最后所有选出的边(包括原先的边)构成的并不一定是一棵树,因为原先的路中可能有环. 所以kruskal中不用判断c

题意,有n个匀速动点,求最小生成树的改变次数. 一句话总结:动态问题的一般做法是先求出一个静态的解,然后求出解发生改变的事件,事件按照时间排序,依次处理. 先求出最开始的最小生成树(MST),当MST中的某条线段v长度被不在MST的线段u取代的时候,最小生成树才会发生变化, 具体来说,已经知道之前的MST,边按照长度排序,在这个时间点之前的瞬间,v一定是MST最长的边,u紧跟在v之后,在这个时间点之后u和v的位置交换了一下, 根据Kruskal算法,对于u和v之前的边没有影响,前面的边连完以后如

Constructing Roads Time Limit: 2000MS   Memory Limit: 65536K               Description There are N villages, which are numbered from 1 to N, and you should build some roads such that every two villages can connect to each other. We say two village A