happy_lcj

题意：有n个村庄，给出每个村庄的坐标和海拔，benifit为两点之间的水平距离，cost为两点的高度差，现要求一棵树使得 cost / benift 最小，即求一个最优比例生成树分析：01规划的应用设x[i]等于1或0, 表示边取或者不取则所求的比率 rate = ∑(cost[i] * x[i]) / ∑(benifit[i] * x[i])

题意：判断最小生成树是否唯一，若唯一，输出最小权值和，否则，输出 Not Unique!判断最小生成树是否唯一的思路：1、对图中的每一条边，扫描其他边，如果存在相同权值的边，则对该边做标记2、然后用Kruskal算法或Prim算法求MST3、求得MST后，如果该MST中未包含做了标记的边，即可判断MST唯一；如果包含做了标记的边，则依次去掉这些边的一条边，再求MST，如果求得的MST权值和原来的MST的权值一样，即可判断MST不唯一。

题意：y行x列的迷宫中，#代表阻隔墙（不可走），空格代表空位（可走），S代表搜索起点（可走） A代表外星人站（可走），现在要从S出发，每次可上下左右移动一格到可走的地方，求到达所有的A 的路线总距离最小值分析：可以先用bfs从上下左右四个方向将所有的A,S两两之间的最短距离，题目的目的是将S与所有的A连通， 使得总距离最小，所以任选一点开始按最小生成树的算法做就行，并非非要从S点开始

链接：zoj 1203题意：输入n个城市的坐标，输出使n个城市连通的最短路线的长度分析：通过坐标可以将两两之间的长度即权值算出，再用最小生成树的算法不过这个题要注意输出时的格式问题，两组数据间要空一行

链接:zoj 1586题意：若两个QS之间要想连网，除了它们间网线的费用外，两者都要买适配器， 求使所有的QS都能连网的最小费用分析：这个除了边的权值外，顶点也有权值，因此要想求最小价值，必须算边及顶点的权值和

链接：poj 2485题意：输入n个城镇相互之间的距离，输出将n个城镇连通费用最小的方案中修的最长的路的长度这个也是最小生成树的题，只不过要求的不是最小价值，而是最小生成树中的最大权值，只需要加个判断比较最小生成树每条边的大小就行

链接:poj 1789题意：除了第一个车型外，其他的都是由另外的车型派生而来。用一个长度为7的字符串代表一种车型， 两种车型之间的distance为两个字符串不同字符的个数，从一种车型派生到另一种车型的代价为它们之间的 distance,求n个车型之间派生的总代价最小为多少？分析：这个题可以转化为最小生成树，每个车型为图的顶点，两两之间的距离（即不同字符的个数）为权值

已知已连通的路的序号，以及未连通的路的费用，求将所有城市连通的最小费用也是将已连通的路的费用记为0，就转化成了基本最小生成树的题不过这题数组要开的大点，不然很容易就RE了、、、

链接：hdu 1879这个题的路分为已修和未修，因此只需将已修的路的费用改为0，就转化成了一般的最小生成树的题了

链接：hdu 1875输入n个岛的坐标，已知修桥100元/米,若能n个岛连通，输出最小费用，否则输出"oh!"限制条件：2个小岛之间的距离不能小于10米，也不能大于1000米分析：因为岛的坐标已知，所以两两之间的距离可以算出，再判断一下距离是否符合条件

链接：hdu 1301题意：n个村庄，已知n-1村庄分别到其他村庄修路的费用，求是n个村庄连通的最小费用分析：这个是最小生成树的题，只不过村庄的编号为A-Z的大写字母，操作比较麻烦，可以将其对应转化为1-26，这样就与普通的最小生成树题一样了

最小生成树的性质MST性质：设G = (V,E)是连通带权图，U是V的真子集。如果(u,v)∈E,且u∈U,v∈V-U,且在所有这样的边中，(u,v)的权c[u][v]最小，那么一定存在G的一棵最小生成树，(u,v)为其中一条边。构造最小生成树，要解决以下两个问题：(1).尽可能选取权值小的边，但不能构成回路（也就是环）。(2).选取n-1条恰当的边以连接网的n个顶点。