HDU 1233 还是畅通工程 (最小生成树)
2024-10-09 01:00:53
还是畅通工程
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 30542 Accepted Submission(s): 13670
Problem Description
某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。
当N为0时,输入结束,该用例不被处理。
当N为0时,输入结束,该用例不被处理。
Output
对每个测试用例,在1行里输出最小的公路总长度。
Sample Input
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
Sample Output
3
5
5
#include <iostream>
#include <cstdio>
#include <string>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <ctime>
using namespace std; const int SIZE = ;
int FATHER[SIZE],N,M,NUM;
int MAP[SIZE][SIZE];
struct Node
{
int from,to,cost;
}G[SIZE * SIZE]; void ini(void);
int find_father(int);
void unite(int,int);
bool same(int,int);
int kruskal(void);
bool comp(const Node &,const Node &);
int main(void)
{
while(scanf("%d",&N) && N)
{
ini();
M = N * (N - ) / ;
for(int i = ;i < M;i ++)
{
scanf("%d%d%d",&G[NUM].from,&G[NUM].to,&G[NUM].cost);
NUM ++;
}
sort(G,G + NUM,comp);
kruskal();
} return ;
} void ini(void)
{
NUM = ;
for(int i = ;i <= N;i ++)
FATHER[i] = i;
} int find_father(int n)
{
if(FATHER[n] == n)
return n;
return FATHER[n] = find_father(FATHER[n]);
} void unite(int x,int y)
{
x = find_father(x);
y = find_father(y); if(x == y)
return ;
FATHER[x] = y;
} bool same(int x,int y)
{
return find_father(x) == find_father(y);
} bool comp(const Node & a,const Node & b)
{
return a.cost < b.cost;
} int kruskal(void)
{
int count = ,ans = ; for(int i = ;i < NUM;i ++)
if(!same(G[i].from,G[i].to))
{
unite(G[i].from,G[i].to);
count ++;
ans += G[i].cost;
if(count == N - )
break;
}
printf("%d\n",ans);
}
最新文章
- Linux命令详解之—tail命令
- 逻辑回归算法的原理及实现(LR)
- 【BZOJ1036】[ZJOI2008]树的统计Count 树链剖分
- [分享]WPF 虚拟键盘
- 如何搭建MVC3与配置models层
- CxImage的使用
- php浮点数计算比较及取整不准确解决方法
- C++外观设计模式模式(三)
- 浅析PageRank算法
- DNS架设准备+申请领域查询授权
- Web开发疑难问题解决方案-(最近更新:2018-11-29)
- His表(简化)
- sticky footer 模板
- linux(centos7) nginx php mysql安装
- Spring与多线程
- 【Alpha】团队课程展示
- 如何在原生工程中引入Cordova工程-for iOS 【转】
- 【Learning】常系数线性齐次递推
- Oracle中查询主键、外键、sequence、表基本信息等
- (15)如何使用Cocos2d-x 3.0制作基于tilemap的游戏:第三部分(完)