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…

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz