hdu 1863 畅通工程 最小生成树模板入门题 prim+kruskal两种算法AC。
畅通工程
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 18866 Accepted Submission(s): 8012
行对应村庄间道路的成本,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间道路的成本(也是正整数)。为简单起见,村庄从1到M编号。当N为0时,全部输入结束,相应的结果不要输出。
3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2 0 100
3 ?
#include <cstdio> #include <algorithm> #include <cstring> #define MAX 110 #define INF 1000000000 using namespace std ; struct Edge{ int x,y,w; }edge[MAX]; int f[MAX] ; bool cmp(const Edge &a ,const Edge &b) { return a.w<b.w ; } void init() { for(int i = 0 ; i < MAX; ++i) { f[i] = i ; } } int find(int x) { int r = x ; while(r != f[r]) { r = f[r] ; } int temp ; while(x != r) { temp = f[x] ; f[x] = r ; x = temp ; } return r ; } int kruskal(int n , int m) { int lowcost[MAX]; bool visited[MAX] ; memset(visited,false,sizeof(visited)) ; sort(edge,edge+n,cmp); for(int i = 0 ; i <= m ; ++i) { lowcost[i] = INF ; } int index = 0 ; init() ; for(int i = 0 ; i < n ; ++i) { int fx = find(edge[i].x) , fy = find(edge[i].y) ; if(fx != fy) { lowcost[index++] = edge[i].w ; f[fx] = fy ; } } int sum = 0 ; for(int i = 0 ; i < m-1 ; ++i) { if(lowcost[i] == INF) { return INF ; } else { sum += lowcost[i] ; } } return sum ; } int main() { int n , m ; while(~scanf("%d%d",&n,&m) && n) { for(int i = 0 ; i < n ; ++i) { int x , y , w ; scanf("%d%d%d",&x,&y,&w) ; edge[i].x = x ; edge[i].y = y ; edge[i].w = w ; } int sum = kruskal(n,m) ; if(sum == INF) { puts("?"); } else { printf("%d\n",sum) ; } } return 0 ; }
prim算法代码:
#include <stdio.h> #include <string.h> #define MAX 110 #define INF 1000000000 int graph[MAX][MAX] ,visited[MAX] ; int prim(int m) { int lowcost[MAX] , closest[MAX]; for(int i = 1 ; i <= m ; ++i) { closest[i] = 1 ; lowcost[i] = graph[1][i] ; } lowcost[1] = 0 ; memset(visited,false,sizeof(visited)) ; visited[1] = true ; for(int i = 0 ; i < m-1 ; ++i) { int min = INF , index=0 ; for(int j = 1 ; j <= m ; ++j) { if(!visited[j] && lowcost[j]<min) { min = lowcost[j] ; index=j ; } } visited[index] = true ; for(int j = 1 ; j <= m ; ++j) { if(!visited[j] && lowcost[j]>graph[index][j]) { lowcost[j] = graph[index][j] ; closest[j] = index ; } } } int sum = 0 ; for(int i = 1 ; i <= m ; ++i) { if(lowcost[i] == INF) { return INF ; } sum += lowcost[i] ; } return sum ; } int main() { int n , m ; while(~scanf("%d%d",&n,&m) && n) { for(int i = 0 ; i <= m ; ++i) { for(int j = 0 ; j <= i ; ++j) { graph[i][j] = graph[j][i] = INF ; } } for(int i = 0 ; i < n ; ++i) { int x , y , w ; scanf("%d%d%d",&x,&y,&w); graph[x][y] = graph[y][x] = w ; } int sum = prim(m) ; if(sum == INF) { puts("?"); } else { printf("%d\n",sum) ; } } return 0 ; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。