公路村村通 （最小生成树）

L3-1 公路村村通  

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式:

输入数据包括城镇数目正整数$N$（$\le 1000$）和候选道路数目$M$（$\le 3N$）；随后的$M$行对应$M$条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到$N$编号。

输出格式:

输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出$-1$，表示需要建设更多公路。

输入样例:

6 15 1 2 5 1 3 3 1 4 7 1 5 4 1 6 2 2 3 4 2 4 6 2 5 2 2 6 6 3 4 6 3 5 1 3 6 1 4 5 10 4 6 8 5 6 3

输出样例:

12

/*准备练习一下最小生成树，所以两种方法都试了一下*/

以下是prim算法：

#include<iostream> #include<cstdio> #include<cstring> #include<stack> #include<cstdlib> #define INF 1000000 using namespace std; int c[1010][1010],lowcost[1010],vis[1010],n,m,sum=0; void init(){ memset(vis,0,sizeof(vis)); memset(c,INF,sizeof(c)); int x,y,d,i; for(i=0;i<m;i++){ cin>>x>>y>>d; c[x][y]=c[y][x]=min(c[x][y],d); } for(i=2;i<=n;i++){ lowcost[i]=c[1][i]; } } int prime(){ int i,j; int p,min; vis[1]=1; for(i=1;i<n;i++){ //处理后面n-1个点 min=INF; p=1; for(j=2;j<=n;j++){ if(lowcost[j]<min && vis[j]==0){ min=lowcost[j]; p=j; } } vis[p]=1; sum+=min; for(j=2;j<=n;j++){ if(lowcost[j]>c[p][j]) lowcost[j]=c[p][j] ; } } } int main(){ cin>>n>>m; init(); prime(); if(sum>=1000000){ cout<<"-1"<<endl; return 0; } cout<<sum<<endl; return 0; }

以下是kruskal算法：

/*kruskal+快排+并查集*/ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #define INF 1000000 using namespace std; struct Edge{ int u; int v; int d; }; int n,m,father[1010],sum=0,num=0; Edge edge[3010]; int find(int x){ int i=x,j; while(x!=father[x]) x=father[x];//找根节点 while(father[i]!=x){ j=father[i]; father[i]=x; i=j; }//压缩路径 return x;//返回根节点 } int Union(int a,int b){//合并：判断新的路能不能加入 int x,y; x=find(a);//这里我写错了，写成x=father[a]，浪费时间调试半天 y=find(b); if(x==y) return 0;//不能 else father[x]=y; return 1;//能 } void init(){ int i; for(i=0;i<m;i++){ cin>>edge[i].u>>edge[i].v>>edge[i].d; } for(i=1;i<=n;i++){ father[i]=i; } } int krustral(){ int i,j; for(i=0;i<m;i++){ if(Union(edge[i].u,edge[i].v)==1){ sum+=edge[i].d; num++; } if(num>=n-1)//表示已经连接n-1条路，n个点连通 break; } } bool cmp(Edge a,Edge b){ return a.d<b.d; } int main(){ cin>>n>>m; init(); sort(edge,edge+m,cmp); krustral(); if(num<n-1){ //注意这里，在prim中是判断sum值是不是超过INF，而kruskal是判断加了几条路，小于n-1条路则不连通 cout<<"-1"<<endl; return 0; } cout<<sum<<endl; return 0; }