H - Agri-Net
Crawling in process... Crawling failed Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u
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.
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(3到100)个村庄数,输入N*N矩阵,a[ i ][ j ]代表 i 村庄到 j 村庄的距离,求能到达所有村庄的最短路径。
题意:
用kruskal算法求最小生成树。
AC:
#include<cstdio> #include<string.h> #include<algorithm> using namespace std; typedef struct { int from,to,len; }r; r road[5000]; //主要路径数组的大小 int root[110]; int cmp(r a,r b) { return a.len<b.len; } int find(int a) { int x=a,t; while(root[x]!=x) x=root[x]; while(x!=a) { t=root[a]; root[a]=x; a=t; } return x; } int main() { int n,i,j,sum=0,length; int pos[110][110]; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) root[i]=i; memset(pos,0,sizeof(pos)); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&pos[i][j]); sum=0; for(i=1;i<n;i++) for(j=i+1;j<=n;j++) { sum++; road[sum].from=i; road[sum].to=j; road[sum].len=pos[i][j]; } sort(road+1,road+sum+1,cmp); length=0; for(i=1;i<=sum;i++) { int fa,fb; fa=find(road[i].from); fb=find(road[i].to); if(fa==fb) continue; else { root[fa]=fb; length+=road[i].len; } } printf("%d\n",length); } return 0; }
总结:
road数组是用来装路径的起点终点和长度的,所以路径条数应该不止顶点数那么多而已。开4000一下就会RE,开5000的时候就AC了,开少于1000的时候就TLE,所以应该要尽量开大点。
相关推荐
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
pku acm 1258 Agri-Net代码 最小生成树的prim算法,有详细的注释
1258:Agri-Net 弗洛伊德思路: 先找到与1相连最短的那条路,然后再更新与1和刚才相连的点每个与其他点最短的路存储,然后再找到下一个点,再找到这三个点与其他点最短路存储,以此类推。 Prim代码: 除了最后一个ac...
阿格里·斯蒂克 农业物联网项目。
北大POJ3414-Pots 解题报告+AC代码
Sen2Agri-package-{{sen2agri_version}}。zip srtm.zip Maja_3.2.2_TM.zip 该脚本可以与外部数据库一起使用。 的角色 nfs-mount:由于大量数据,特定于我们的项目使用NFS文件系统 maja:需要Sen2Agri服务 sen2...
农业地图 一些用于可视化农业植物间距的代码 要求 matplotlib ... 与运行python agri_map.py默认如图所示运行,其结果。 也可以与命令行参数一起运行以修改输出(与-h标志一起运行以查看可用选项)。
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 ...
风云四号A星 HDF文件 用查找表 将行列号转成 NC格式的等经纬数据; 代码不开源 需要的话 联系邮箱258466895@qq.com
poj经典数据结构题目解题报告,包括经典的数据结构题目10多道,可以作为学习数据结构系统的资料,包括题目: Pku acm 3253 Fence Repair Pku acm 1861 NetWork Pku acm 2485 Highways Pku acm 1258 Agri-...
农业易货项目 巴丹半岛州立大学BS信息技术计划的顶点项目
python库。 资源全名:agri_tech-0.1.6-py2.py3-none-any.whl
资源来自pypi官网。 资源全名:agri_tech-0.1.7-py2.py3-none-any.whl
它的方法是与非政府组织Nutri-Fresh Farm&Agri-Hub合作,该非政府组织是由肯尼亚的自给自足农民和青年创建农业企业家的。 每个家庭签署了《家禽项目贷款协议》,其中规定他们有义务无偿还以成年家禽的形式支付雏鸡...
资源来自pypi官网。 资源全名:agri_tech-0.1.6.tar.gz
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 ...
语言:English ...干针治疗,肌肉刺激(IMS)也称为肌肉内刺激的治疗。该方法已由加拿大麻醉医生开发。疼痛是一种方法,其中可以在不使用的情况下处理疼痛。可用于治疗急性和慢性疼痛。特别是,它用于治疗肌肉和骨骼疼痛...
Ask-Agri小型项目::使用ML进行农作物产量预测