题意:车的类型用字符串来描述,两个汽车类型的距离定义为其字符串中不同字符的个数,给定所有的车的类型,求车之间的派生关系,使得总的距离最短,派生关系质量分最大
算法:转化为图论问题,结点对应不同的汽车类型,边的权值就是不同结点字符串距离值,求最小生成树即可(因为题目说明了每个汽车只有一种汽车派生出)
Source Code
Problem: 1789
|
|
User:
yangliuACMer
|
Memory: 15688K |
|
Time: 422MS |
Language: C++ |
|
Result: Accepted
|
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1705139
NULL 博文链接:https://128kj.iteye.com/blog/1704752
北大POJ1789-Truck History【Prim】 解题报告+AC代码
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
NULL 博文链接:https://200830740306.iteye.com/blog/603493
poj1789 Truck History prim
北大POJ2485-Highways【Prim】 解题报告+AC代码
poj 1789 Truck History.md
(3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序 (poj1094) (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) .....
北大POJ1016-Numbers That Count【字符串处理】 解题报告+AC代码
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
最小度限制生成树的求法也不是很难,先把度被限制的那个点(s点)去掉,求一次MST,然后把s到各个连通分量的最小权值的边加上,然后继续加边看看能否使生成树权减小(详见解题报告)。
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
度限制最小生成树代码 摘自POJ1639代码
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
北大POJ初级-图算法 解题报告+AC代码