Problem 2902 --3.1.1 Agri-Net

2902: 3.1.1 Agri-Net

上一题 正确率: $75.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $4$ 正确数量 $3$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 usaco 图论

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

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.

Output

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 Input复制

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

Sample Output复制

28

推荐代码 查看2902 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$3 $ms] 计爱玲 448854 2019-07-24 13:48:07
内存最少[$1204 $KB] 梦尘 694768 2020-12-30 22:43:38
第一AC 计爱玲 448854 2019-07-24 13:48:07
第一挑战 计爱玲 448839 2019-07-24 11:06:21

赛题来源/所属竞赛 usaco training usaco Training

竞赛编号 竞赛名称 竞赛时间 访问比赛