poj 2031 题意：三维空间中n个球要相连。。。通路的代价是距离。。。如果球相交（切）或者包含那么不用建通路就能联系。。。问联系所有球的最小代价。。。 思路：裸的最小生成树。。。。先预处理球和球表面的距离。。。距离是负数的处理成0.。。然后mst搞之。。。不算CE的话是1A.... /* *********************************************** Author :111qqz Created Time :2016年07月14日 星期四 15时44分53秒 File Name :code/poj/2031.cpp …

poj1789题目链接 题意：其实题目不难理解。。。直接按照定义去搞就行了。。。 思路：由于距离在分母上。。所以要quality最大。。。就是要分母最小。。。 然后由于题目中说每一种类型的type只能由其他一种派生出来。。。我们可以把这个派生关系看做一条边。。。把每种类型看成点。。 这样就构成了一棵树。。。先o(nn7)预处理出权值。。。然后最小生成树即可。。。 这种给了坐标距离作为权值的图一定是稠密图。。。图小用kruskal糊弄一下就过去了。。。图大的话还是乖乖的用prim吧。。。 然而仍然 TLE???wtf?? 最后发现。。因为我习惯用string...但是又怕卡cin...所以做法是scanf读入字符数组然后再赋值 …

Poj2349题目链接 题意：给出n个点坐标。。。然后可以建s个卫星基站。。。有卫星基站的地方之间可以互相免费通信。。现在要建一些无线电通讯线路（不同于卫星基站，是另一种通信方式），两个点之间线路的代价是他们的距离。。。问最小距离是多少。。。使得任意两个点之间都可以直接或者间接联系。。。 思路：mst即可。。。s个卫星基站可以减少s-1条最大的边。。。多组数据。。m忘记清0.。。re一发。。。2a /* *********************************************** Author :111qqz Created Time :2016年07月13日 星期三 16时35分42秒 File Name …

poj1751题目链接 题意：一开始有一些边，然后添加一些边，使得代价之和最小。 思路：先把给定的边merge掉。。然后计算其余可以添加的边。。。接下来就是最小生成树。。。 然而因为多开了一个750*750的数组空间被卡了常。。。毫无人性。。。。 /* *********************************************** Author :111qqz Created Time :2016年07月13日 星期三 19时53分29秒 File Name :code/poj/1751.cpp ************************************************ */ #include …

poj1679 题意：问最小生成树是否唯一。。 思路：求一下次小生成树。。。如果无解，或者次小生成树的权值之和和最小生成树的权值之和不同，那么唯一，否则不唯一。1A /* *********************************************** Author :111qqz Created Time :2016年07月12日 星期二 16时16分52秒 File Name :code/poj/1679.cpp ************************************************ */ #include <cstdio> #include <cstring> …

URAL1416 题意：次小生成树模板题 思路：用Kruskal求最小生成树，标记用过的边。求次小生成树时，依次枚举用过的边，将其去除后再求最小生成树，得出所有情况下的最小的生成树就是次小的生成树。复杂度o(m2)。。。貌似有其他优化。。。 写的时候。。因为点数是500。。我把边集的数组大小开成了500.。。交了10遍越界才意识到问题在哪里。。。真的是智商掉线啊orz... /* *********************************************** Author :111qqz Created Time :2016年07月11日 星期一 20时44分28秒 File Name …