题目描述:
一个Internet站点集合,可以用如下的方式来描述站点和站点之间的链接引用关系:
s 1 2 3 4
1 / 4 0 3
2 3 / 4 5
3 2 2 / 2
4 6 1 4 /
其中与s(site)同行和同列的数字都表示站点号,其他每个数字表示一个站点到另一个站点的超文本链接数。如果站点A有到另一个站点B的直接链接或间接(指通过一个或多个直接链接)链接,则称站点A有到站点B的访问关系,或称站点B可以被站点A访问到。例如,上面描述了一个有4个站点链接关系的站点集合,第一行 / 4 0 3 表示站点1到站点1,2,3,4的超文本链接数。
s 1 2 3 4
1 / 4 0 3
2 3 / 4 5
3 2 2 / 2
4 6 1 4 /
其中与s(site)同行和同列的数字都表示站点号
请编写程序:
1) 将一个有N个站点的集合划分成满足下面所有条件的站点子集
a) 当任一子集中的站点数大于1时,该子集内至少存在一个站点有到该子
b) 当任一子集中的站点数大于1时,该子集内的任一站点至少可以被该子
c) 两个不同子集中的任意两个站点之间不存在任何访问关系。
2) 裁减这些子集内的站点之间现有的链接关系,使得被裁减后的各子集内
假如上面的站点集合是这N个站点集合中的一个子集
s 1 2 3 4
1 / 0 0 0
2 0 / 0 0
3 2 0 / 2
4 0 1 4 /
这里,站点4可以访问到站点3和2,站点4也可以访问到站点1
输入数据:
程序读入已被命名为sites.txt的完全如上所示的N*N矩阵的输入数据文本文件,N不大于10万(N即为行数和列数),输入文件的每一行的列和列之间用一个\t分隔,行和行之间用\n分隔。
输出数据:
按行输出满足题目要求的每个子集内的站点数以及裁减后的最小链接总数之和,数和数之间都以一个空格分隔。如上述子集和最小链接总数为:
1 2 3 4 9
如果输入数据无满足题目要求的子集存在,则输出NONE。
1 2 3 4 9
如果输入数据无满足题目要求的子集存在,则输出NONE。
评分标准:
在结果正确的前提下,会考虑程序的运行时间。我们会用两个不同的输入数据文件(一个简单一个复杂)进行测试,简单的输入数据产生的程序输出B
第二题(题目原文未保存...)
第二题(题目原文未保存...)