poj 1258 Agri-Net 最小生成树 kruskal
2024-10-19 05:30:28
Agri-Net
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 33733 | Accepted: 13539 |
Description
Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.
Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms.
Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm.
The distance between any two farms will not exceed 100,000.
Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms.
Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm.
The distance between any two farms will not exceed 100,000.
Input
The input includes several cases. For each case, the first line contains the number of farms, N (3 <= N <= 100). The following lines contain the N x N conectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines
of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem.
of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem.
Output
For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.
Sample Input
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
Sample Output
28
给n个点,求最小生成树。这次用的kruskal + 并查集 实现的
#include<stdio.h>
#include<algorithm>
using namespace std;
struct Edge
{
int s, t, pow;
};
Edge edge[25010];
int total;
int n;//输入点的个数
int father[500];
//并查集模板
int getfather(int p)
{
if(father[p] == p)
return p;
else
return father[p] = getfather(father[p]);
}
void merge_(int a, int b)
{
a = getfather(a);
b = getfather(b);
if(a == b)
return ;
else
father[a] = b;
}
void init_set()
{
int i;
for(i = 0; i <= n; i++)
father[i] = i;
}
//kruskal
bool cmp(Edge a, Edge b)
{
return a.pow < b.pow;//´ÓСµ½´óÅÅÐò
}
int kruskal()
{
sort(edge, edge + total, cmp);
bool used[500] = {0};
int i;
int count = 0;
int ans = 0;
init_set();
for(i = 1; i < total; i++)
{
if(getfather(edge[i].s) != getfather(edge[i].t))
{
merge_(edge[i].s, edge[i].t);
ans += edge[i].pow;
count ++;
if(count == n - 1)
break;
}
}
return ans;
}
void addedge(int s, int t, int pow)
{
edge[total].s = s;
edge[total].t = t;
edge[total].pow = pow;
total ++;
}
int main()
{
// freopen("in.txt", "r", stdin);
while(scanf("%d", &n) != EOF)
{
int i;
total = 0;
for(i = 1; i <= n; i++)
{
int j;
for(j = 1; j <= n; j++)
{
int num;
scanf("%d", &num);
if(i == j)
continue;
addedge(i, j, num);
}
}
printf("%d\n", kruskal());
}
return 0;
}
最新文章
- configure Git to accept a particular self-signed server certificate for a particular https remote
- 2016ACM/ICPC亚洲区沈阳站-重现赛赛题
- 基于bshare分享平台,在一个页面上实现多个不同内容的web分享
- 编写高质量JS代码的68个有效方法(九)
- Object-C 内存管理及对象
- hdu-5703 Desert(水题)
- php正则表达式总结第1弹
- prefix和unprefix
- [AngularJS + Webpack] Uglifying your JavaScript
- QLCDNumber设置背景色和显示数字颜色
- 高性能的JavaScript--加载和执行[转]
- About Unixstickers - Unixstickers - stickers on unix, programming, software, development and open source
- urllib2 之info 学习
- heapsort(Java)(最小堆)
- ROM、PROM、EPROM、EEPROM、FLASH ROM、FLASH、eMMC
- .NET Core1.1+VS2017RC+MySQL+EF搭建多层Web应用程序
- Beta阶段冲刺-6
- 分享一个使用 vue.js 开发的网站
- oracle数据库之操作总结
- js LINQ教程
热门文章
- 你了解System.out.println()的真正含义吗?
- (转)Android-Mac电脑如何进行APK反编译-使用apktool、jd-gui
- Neutron分析(1)——简介
- 剑指offer系列31-----二叉树的下一个节点
- Dell R410 broadcom网卡驱动更新失败
- datagridview 列位置 设置顺序与加载显示顺序不一致
- 36. Valid Sudoku
- flash bulider 生成app无法安装在xcode模拟器上
- 用CRT connect MongoDB 使用Backspace无效
- [复变函数]第10堂课 3.2 Cauchy 积分定理