poj 2031 Building a Space Station (最小生成树)

poj 2031

 

题意:三维空间中n个球要相连。。。通路的代价是距离。。。如果球相交(切)或者包含那么不用建通路就能联系。。。问联系所有球的最小代价。。。

思路:裸的最小生成树。。。。先预处理球和球表面的距离。。。距离是负数的处理成0.。。然后mst搞之。。。不算CE的话是1A….

 

 

poj 1789 Truck History (mst,prim)

poj1789题目链接

 

题意:其实题目不难理解。。。直接按照定义去搞就行了。。。

思路:由于距离在分母上。。所以要quality最大。。。就是要分母最小。。。

然后由于题目中说每一种类型的type只能由其他一种派生出来。。。我们可以把这个派生关系看做一条边。。。把每种类型看成点。。

这样就构成了一棵树。。。先o(n*n*7)预处理出权值。。。然后最小生成树即可。。。

这种给了坐标距离作为权值的图一定是稠密图。。。图小用kruskal糊弄一下就过去了。。。图大的话还是乖乖的用prim吧。。。

然而仍然 TLE???wtf??

 

最后发现。。因为我习惯用string…但是又怕卡cin…所以做法是scanf读入字符数组然后再赋值给string..

2016-07-14 00-56-11 的屏幕截图

 

然而这种操作不知为何神tm慢。。。。。(求指教)

 

以至于:2016-07-14 01-06-47 的屏幕截图

要知道。。。这题时限2s啊。。。为毛能差1s多。。。也就是说时间的瓶颈完全是在读入了orz…

 

 

 

poj 2349 Arctic Network (mst)

Poj2349题目链接

题意:给出n个点坐标。。。然后可以建s个卫星基站。。。有卫星基站的地方之间可以互相免费通信。。现在要建一些无线电通讯线路(不同于卫星基站,是另一种通信方式),两个点之间线路的代价是他们的距离。。。问最小距离是多少。。。使得任意两个点之间都可以直接或者间接联系。。。

思路:mst即可。。。s个卫星基站可以减少s-1条最大的边。。。多组数据。。m忘记清0.。。re一发。。。2a

 

poj 1751 Highways (最小生成树,空间卡常数有毒啊)

poj1751题目链接

题意:一开始有一些边,然后添加一些边,使得代价之和最小。

思路:先把给定的边merge掉。。然后计算其余可以添加的边。。。接下来就是最小生成树。。。

然而因为多开了一个750*750的数组空间被卡了常。。。毫无人性。。。。

 

poj 1679 The Unique MST (判断mst的唯一性,次小生成树)

poj1679

题意:问最小生成树是否唯一。。

思路:求一下次小生成树。。。如果无解,或者次小生成树的权值之和和最小生成树的权值之和不同,那么唯一,否则不唯一。1A

 

ural 1416. Confidential (次小生成树模板题)

URAL1416
题意:次小生成树模板题

思路:用Kruskal求最小生成树,标记用过的边。求次小生成树时,依次枚举用过的边,将其去除后再求最小生成树,得出所有情况下的最小的生成树就是次小的生成树。复杂度o(m2)。。。貌似有其他优化。。。

 

写的时候。。因为点数是500。。我把边集的数组大小开成了500.。。交了10遍越界才意识到问题在哪里。。。真的是智商掉线啊orz…