{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"Luke想要将他家中的计算机网络从10mbs升级到100mbs。他现有的网络使用的是10base2(同轴)电缆,可以将任意数量的计算机线性连接在一起。Luke特别自豪地解决了一个棘手的NP完全问题,以最小化总电缆长度。\n\u003cbr\u003e不幸的是,Luke不能继续使用他现有的电缆。100mbs系统使用的是100baseT(双绞线)电缆。每根100baseT电缆只能连接两个设备:要么是两个网络卡,要么是一个网络卡和一个集线器(hub)。Luke有两种选择:他可以购买2N-2个网络卡,并通过在每台计算机中插入一个或多个卡来将他的N台计算机连接在一起。或者他可以购买N个网络卡和一个集线器,并将他的N台计算机连接到集线器上。第一种方法需要Luke配置操作系统以转发网络流量。然而,安装了Winux 2007.2后,Luke发现网络转发不再起作用。他无法弄清如何重新启用转发,而且他从未听说过Prim或Kruskal,所以他选择了第二种方法:N个网络卡和一个集线器。\n\u003cbr\u003e\n\u003cbr\u003e\nLuke住在一个阁楼里,所以准备布置电缆并将集线器放在任何地方。但他不想移动他的计算机。他希望最小化他必须购买的电缆总长度。"}},{"title":"输入","value":{"format":"HTML","content":"输入的第一行包含一个正整数N,表示计算机的数量,N \u003c\u003d 100。接下来的N行每行给出一个计算机在房间内的(x,y)坐标(单位:毫米)。所有坐标都是0到10,000之间的整数。"}},{"title":"输出","value":{"format":"HTML","content":"输出包括一个数字,表示电缆段的总长度,四舍五入到最近的毫米。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n0 0\r\n0 10000\r\n10000 10000\r\n10000 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e28284\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}