1807: 猪仙修桥
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:2
解决:0
题目描述
猪仙多次修桥,已经小有名气了,于是,不断有人来找猪仙修桥。一天,猪仙接到了这样的任务。在一片大海上有N座岛屿,需要使它们联通。但是由于经费问题,岛上的居民想在任意两点间距离最短的前提下,用尽可能少的投资把各个岛屿连接起来。需要注意的是,并不是任两个岛屿间都能直接连接,且花费和距离成正比。
但是大家知道,猪仙实际上是不会修桥的,所以他需要大家的帮助。
但是大家知道,猪仙实际上是不会修桥的,所以他需要大家的帮助。
输入
第一行是一个数N(n<100)表示有N个岛屿。
以下N行每行有N个数,第i行第j个数表示岛屿i和岛屿j间建路的花费Wij(0<Wij<10000,Wij=Wji),非正数表示两地不可直连。输入数据保证有解。
以下N行每行有N个数,第i行第j个数表示岛屿i和岛屿j间建路的花费Wij(0<Wij<10000,Wij=Wji),非正数表示两地不可直连。输入数据保证有解。
输出
第一行输出总花费
然后输出N行,每行个数,第i行第j个数表示岛屿i到岛屿j的路。用1表示这选取条路,0则不选
然后输出N行,每行个数,第i行第j个数表示岛屿i到岛屿j的路。用1表示这选取条路,0则不选
样例输入 复制
3
0 2 1
2 0 3
1 3 0
样例输出 复制
3
0 1 1
1 0 0
1 0 0