最小生成树总结+例题

最小生成树是连接一个图中所有点的最短距离。克鲁斯卡尔算法找到权值最小的边相连但要确保连上这条边后不会构成回路。这里的判断回路用到并查集。Prim算法随便选一个点作为起点找到与这个点相连的权值最小的边将其连接用一个数组标记哪些顶点已经加入了生成树。继续找离这两个点权值最小的边将其连接重复n-1次操作。这里的算法与Dijkstra算法相似这里计算的最短距离是“生成树”到各个顶点的距离。例题1.畅通工程再续 HDU - 1875链接相信大家都听说一个“百岛湖”的地方吧百岛湖的居民生活在不同的小岛中当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖发展首先要解决的问题当然是交通问题政府决定实现百岛湖的全畅通经过考察小组RPRush对百岛湖的情况充分了解后决定在符合条件的小岛间建上桥所谓符合条件就是2个小岛之间的距离不能小于10米也不能大于1000米。当然为了节省资金只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。Input输入包括多组数据。输入首先包括一个整数T(T 200)代表有T组数据。每组数据首先是一个整数C(C 100),代表小岛的个数接下来是C组坐标代表每个小岛的坐标这些坐标都是 0 x, y 1000的整数。Output每组输入数据输出一行代表建桥的最小花费结果保留一位小数。如果无法实现工程以达到全部畅通输出”oh!”.Sample Input2210 1020 2031 12 21000 1000Sample Output1414.2oh!#includeiostream #includecstdio #includecstring #includequeue #includecmath #includealgorithm using namespace std; int f[105]; int n; struct node{ int x,y; double z; }; int a[105][105]; double diss(node a,node b){ return sqrt((a.x-b.x)*(a.x-b.x)(a.y-b.y)*(a.y-b.y)); } int getf(int x){ if(xf[x])return x; return f[x]getf(f[x]); } double cmp(node a,node b){ return a.zb.z; } int main(){ int c; cinc; while(c--){ scanf(%d,n); node e[10005],d[10005]; int m1; for(int i1;in;i){ scanf(%d%d,e[i].x,e[i].y); for(int j1;ji;j){ double cdiss(e[i],e[j]); if(c10c1000){ d[m].xi; d[m].yj; d[m].zc; m; d[m].xi; d[m].yj; d[m].zc; m; } } } sort(d1,dm,cmp); memset(f,0,sizeof(f)); for(int i1;in;i){ f[i]i; } double ans0; for(int i1;im;i){ int xgetf(d[i].x); int ygetf(d[i].y); if(xy)continue; f[x]y; ansd[i].z; // coutansaaendl; } ans*100; if(ans!0)printf(%.1lf\n,ans); else printf(oh!\n); } return 0; }2. Highways POJ - 1751The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has a very poor system of public highways. The Flatopian government is aware of this problem and has already constructed a number of highways connecting some of the most important towns. However, there are still some towns that you can’t reach via a highway. It is necessary to build more highways so that it will be possible to drive between any pair of towns without leaving the highway system.Flatopian towns are numbered from 1 to N and town i has a position given by the Cartesian coordinates (xi, yi). Each highway connects exaclty two towns. All highways (both the original ones and the ones that are to be built) follow straight lines, and thus their length is equal to Cartesian distance between towns. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways.The Flatopian government wants to minimize the cost of building new highways. However, they want to guarantee that every town is highway-reachable from every other town. Since Flatopia is so flat, the cost of a highway is always proportional to its length. Thus, the least expensive highway system will be the one that minimizes the total highways length.InputThe input consists of two parts. The first part describes all towns in the country, and the second part describes all of the highways that have already been built.The first line of the input file contains a single integer N (1 N 750), representing the number of towns. The next N lines each contain two integers, xi and yi separated by a space. These values give the coordinates of i th town (for i from 1 to N). Coordinates will have an absolute value no greater than 10000. Every town has a unique location.The next line contains a single integer M (0 M 1000), representing the number of existing highways. The next M lines each contain a pair of integers separated by a space. These two integers give a pair of town numbers which are already connected by a highway. Each pair of towns is connected by at most one highway.OutputWrite to the output a single line for each new highway that should be built in order to connect all towns with minimal possible total length of new highways. Each highway should be presented by printing town numbers that this highway connects, separated by a space.If no new highways need to be built (all towns are already connected), then the output file should be created but it should be empty.Sample Input91 50 03 24 55 10 45 21 25 331 39 71 2Sample Output1 63 74 95 78 3题意已知有n个城镇及它们的坐标且已有m个条路已经修通输出若使所有的城镇连接起来并且使所修公路的距离最短需要修建哪些公路。prim算法适用于稠密图对于已联通的两点距离为零。建图时不需要开根号。#includeiostream #includecstdio #includecstring using namespace std; const int inf0x3f3f3f; struct node{ int x,y; }a[755]; int n,m; int diss(node a,node b){ return (a.x-b.x)*(a.x-b.x)(a.y-b.y)*(a.y-b.y); } int vis[755],mp[755][755],dis[755],e[755]; void prim(){ for(int i1;in;i){ int minninf; int point_minn; for(int j1;jn;j){ if(vis[j]0minndis[j]){ minndis[j]; point_minnj;//找到离“生成树”最近的点 } } vis[point_minn]1; for(int k1;kn;k){ if(vis[k]0dis[k]mp[point_minn][k]){ e[k]point_minn;//在k与point_minn建立一条边 dis[k]mp[point_minn][k]; } } if(mp[e[point_minn]][point_minn]){ printf(%d %d\n,e[point_minn],point_minn); } } } int main(){ scanf(%d,n); for(int i1;in;i){ scanf(%d%d,a[i].x,a[i].y); for(int j1;ji;j){ mp[i][j]mp[j][i]diss(a[i],a[j]); } mp[i][i]inf; } scanf(%d,m); int xx,yy; for(int i1;im;i){ scanf(%d%d,xx,yy); mp[xx][yy]mp[yy][xx]0; } memset(vis,0,sizeof(vis)); vis[1]1; for(int i1;in;i){ dis[i]mp[1][i]; e[i]1; } prim(); }3.P1265 公路修建某国有n个城市它们互相之间没有公路相通因此交通十分不便。为解决这一“行路难”的问题政府决定修建公路。修建公路的任务由各城市共同完成。修建工程分若干轮完成。在每一轮中每个城市选择一个与它最近的城市申请修建通往该城市的公路。政府负责审批这些申请以决定是否同意修建。政府审批的规则如下1如果两个或以上城市申请修建同一条公路则让它们共同修建2如果三个或以上的城市申请修建的公路成环。如下图A申请修建公路ABB申请修建公路BCC申请修建公路CA。则政府将否决其中最短的一条公路的修建申请3其他情况的申请一律同意。一轮修建结束后可能会有若干城市可以通过公路直接或间接相连。这些可以互相连通的城市即组成“城市联盟”。在下一轮修建中每个“城市联盟”将被看作一个城市发挥一个城市的作用。当所有城市被组合成一个“城市联盟”时修建工程也就完成了。你的任务是根据城市的分布和前面讲到的规则计算出将要修建的公路总长度。思路裸的prim算法与上题不同的是这个不能用5000*5000的矩阵将权值存起来否则会mle只需要找到这个点时再计算权值就好了。#includeiostream #includecstring #includecstdio #includecmath using namespace std; const int maxn5001; int n,x[maxn],y[maxn]; double cnt,d[maxn]; bool b[maxn]; double dis(int i,int j) { return sqrt((double)(x[i]-x[j])*(x[i]-x[j])(double)(y[i]-y[j])*(y[i]-y[j])); } int main() { scanf(%d,n); for(int i1;in;i) scanf(%d%d,xi,yi); for(int i1;in;i) d[i]dis(1,i); int k; for(int i1;in-1;i) { double mn1e9; for(int j1;jn;j) if(d[j]d[j]mn) { mnd[j]; kj; } d[k]0; cntmn; for(int j1;jn;j) if(dis(k,j)d[j]) d[j]dis(k,j); } printf(%.2f\n,cnt); return 0; }