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