Skip to content

13033: 【原3033】荀彧的忧郁

题目

题目描述

author: csy 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3033

题目描述

荀彧最近心情极差,他正为曹操的任务头痛不已,曹操刚刚征服的蛮夷之地,是个闭塞的区域。 这个区域中分布有十分多的部落,而部落之间无法直接通行。但若要保证这一地区的安定,则需要在他们之间铺设道路,以便从任何一个部落都能抵达任意其他部落。 铺设两个不同部落之间的道路,需要一些不同的代价,而曹操最近已经穷得以盗墓充当军费,所以并无多余的钱粮,所以命令他以最少的代价,完成这项任务,否则,移灭三族。 为了拯救这位王佐之才,请你帮他解决这个难题。

【输入数据】

第一行: 部落的个数,N(1≤N≤1000)
此后N行:一个N*N的矩阵,表示每个部落之间铺设道路的代价。

【样例输入】

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

【输出数据】

一个整数,代价的最小值。

【样例输出】

28

提示:最小生成树

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!