POJ 1258 Agri-Net
发布日期:2022-02-05 18:27:26
浏览次数:16
分类:技术文章
本文共 1899 字,大约阅读时间需要 6 分钟。
Agri-Net
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 34245 | Accepted: 13772 |
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.
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.
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
40 4 9 214 0 8 179 8 0 1621 17 16 0
Sample Output
28
最小生成树
给的邻接矩阵 蒟蒻不会prim怎么办
转化成临界表kruskal吧。。。
还要注意是多组数据 注意初始化
#include#include #include #include using namespace std;struct self{int x,y,w;}s[10011];int g[101][101];int f[101];int find(int i){return i==f[i]?i:f[i]=find(f[i]);}int m,n,a,b,c,z;int cmp(self a1,self a2){ if(a1.w==a2.w) { if(a1.y==a2.y)return a1.x
转载地址:https://blog.csdn.net/li412302070/article/details/12773721 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月11日 02时15分56秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Android Studio 3.6 发布啦,快来围观
2019-04-26
Fuchsia 是什么?Fuchsia OS 的未来如何?
2019-04-26
Fuchsia 的开发语言政策与解读
2019-04-26
Flutter 中的图文混排与原理解析
2019-04-26
Spuernova 是如何提升 Flutter 的生产力
2019-04-26
Flutter 官方尝试放只“鸽子”来简化Native插件开发
2019-04-26
Flutter完整开发实战详解(二十一、 Flutter 画面渲染的全面解析)
2019-04-26
Flutter 上的一个 Bug 带你了解键盘与路由的另类知识点
2019-04-26
Flutter 上默认的文本和字体知识点
2019-04-26
Android Studio 4.0 稳定版发布了
2019-04-26
带你深入理解 Flutter 中的字体“冷”知识
2019-04-26
给 Android 和 iOS 开发人员不一样的 Flutter 基础讲解
2019-04-26
不一样角度带你了解 Flutter 中的滑动列表实现
2019-04-26
谷歌将正式推出 Fuchsia OS,已有适配设备
2019-04-26
带你深入 Dart 解析一个有趣的引用和编译实验
2019-04-26
微博的文本编辑和显示(emoji表情,@某人、链接高亮点击)
2019-04-26
Android 实现视屏播放器、边播边缓存功能、外加铲屎(IJKPlayer)
2019-04-26
Android MP3录制,波形显示,音频权限兼容与播放
2019-04-26