Russ Cox
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.
PROGRAM NAME: agrinet
INPUT FORMAT
Line 1: | The number of farms, N (3 <= N <= 100). |
Line 2..end: | The subsequent lines contain the N x N connectivity 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. |
SAMPLE INPUT (file agrinet.in)
4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0
OUTPUT FORMAT
The single output contains the integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.
SAMPLE OUTPUT (file agrinet.out)
28
题意:
给出 N (3 ~ 100),后给出矩阵 N X N,代表 i 到 j 的距离。求最小生成树。
思路:
Kruskal。刚学并查集的时候写过一遍,重新写了一遍,对比下代码风格。
AC:
/* TASK:agrinet LANG:C++ ID:sum-g1 */ #include <cstdio> #include <algorithm> using namespace std; typedef struct { int u, v, l; }node; node no[10005]; int root[105]; int cmp(node a, node b) { return a.l < b.l; } int Find(int x) { return x == root[x] ? x : root[x] = Find(root[x]); } int main() { freopen("agrinet.in", "r", stdin); freopen("agrinet.out", "w", stdout); int n, sum = 0; scanf("%d",&n); for (int i = 1; i <= n; ++i) root[i] = i; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) { int ans; scanf("%d",&ans); if (ans) { no[sum].u = i; no[sum].v = j; no[sum].l = ans; sum++; } } sort(no,no + sum,cmp); int ans = 0; for (int i = 0; i < sum; ++i) { int fa = Find(no[i].u); int fb = Find(no[i].v); if (fa != fb) { ans += no[i].l; root[fa] = fb; } } printf("%d\n", ans); return 0; }
相关推荐
pku acm 1258 Agri-Net代码 最小生成树的prim算法,有详细的注释
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
1258:Agri-Net 弗洛伊德思路: 先找到与1相连最短的那条路,然后再更新与1和刚才相连的点每个与其他点最短的路存储,然后再找到下一个点,再找到这三个点与其他点最短路存储,以此类推。 Prim代码: 除了最后一个ac...
北大POJ3414-Pots 解题报告+AC代码
阿格里·斯蒂克 农业物联网项目。
在的底部,有一个示例性地块间距图,其中散布了临时和永久(TODO)遮荫树的可可树。 与运行python agri_map.py默认如图所示运行,其结果。 也可以与命令行参数一起运行以修改输出(与-h标志一起运行以查看可用选项)...
Ansible角色,用于简化Sen2Agri服务的安装过程。 这些脚本是为使用Sen2Agri所需的Centos7而量身定制的。 为了运行脚本,您需要下载 Sen2Agri-package-{{sen2agri_version}}。zip srtm.zip Maja_3.2.2_TM.zip 该...
my_vue 一个Vue.js项目构建设置# install dependenciesnpm install# serve with hot reload at localhost:8080npm run dev# build for production with minificationnpm run build# build for production and view ...
python库。 资源全名:agri_tech-0.1.6-py2.py3-none-any.whl
资源来自pypi官网。 资源全名:agri_tech-0.1.7-py2.py3-none-any.whl
风云四号A星 HDF文件 用查找表 将行列号转成 NC格式的等经纬数据; 代码不开源 需要的话 联系邮箱258466895@qq.com
农业易货项目 巴丹半岛州立大学BS信息技术计划的顶点项目
资源来自pypi官网。 资源全名:agri_tech-0.1.6.tar.gz
poj经典数据结构题目解题报告,包括经典的数据结构题目10多道,可以作为学习数据结构系统的资料,包括题目: Pku acm 3253 Fence Repair Pku acm 1861 NetWork Pku acm 2485 Highways Pku acm 1258 Agri-...
最近,Nutri-Fresh Farm和Agri-Hub的总监Simon Wachieni确认,到目前为止,所有涉入的家庭都在出售鸡蛋,并作为自身的常规蛋白质来源,他们通过自己孵化小鸡增加了资产,并且他们正在偿还贷款。 我们的最终结论是,...
肌肉和骨骼系统疼痛是由于生成的干扰。姿势障碍引起的痛苦在使用公共交通的人中更为常见。由于这些原因,生活在伊斯坦布尔等大城市的人是一种无毒的治疗方法,可用于肌肉疼痛的溶液。这种治疗中使用的针不是正常注射...
Agri-antibiotics 2507 is a new kind of agri-antibiotics against Oomyces,its analysismethod was established with high performance liquid chromatography ( HPLC) . Agri-antibiotics 2507 could be ...
Ask-Agri小型项目::使用ML进行农作物产量预测