| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 544 人关注过本帖
标题:[求助]一个关于图的经典问题
只看楼主 加入收藏
jinmu0755
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2005-9-24
收藏
 问题点数:0 回复次数:1 
[求助]一个关于图的经典问题

题目描述

一个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的超文本链接数。

请编写程序: 1) 将一个有N个站点的集合划分成满足下面所有条件的站点子集(这些子集的union组成了该N个站点集合): a) 当任一子集中的站点数大于1时,该子集内至少存在一个站点有到该子集内所有其他站点的访问关系;

b) 当任一子集中的站点数大于1时,该子集内的任一站点至少可以被该子集内的某一站点访问到; c) 两个不同子集中的任意两个站点之间不存在任何访问关系。 2) 裁减这些子集内的站点之间现有的链接关系,使得被裁减后的各子集内的站点依然可以满足上述所有条件,同时使得子集内的站点之间的链接总数相加之和为最小。

假如上面的站点集合是这N个站点集合中的一个子集,它满足了条件a):4可以访问到3,也可以访问到2和1;也满足了条件b):站点4可以被站点3访问到,等等。对该站点集合进行裁减使其仍然满足条件a和b,并使得其链接总数之和为最小的结果为: 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(通过站点3间接访问);此外,站点3可以访问到站点4;最小链接总数相加为2+2+1+4=9。

输入数据

程序读入已被命名为sites.txt的完全如上所示的N*N矩阵的输入数据文本文件,N不大于10万(N即为行数和列数),输入文件的每一行的列和

列之间用一个\t分隔,行和行之间用\n分隔。

输出数据

按行输出满足题目要求的每个子集内的站点数以及裁减后的最小链接总数之和,数和数之间都以一个空格分隔。如上述子集和最小链接总数为: 1 2 3 4 9 如果输入数据无满足题目要求的子集存在,则输出NONE。

评分标准

在结果正确的前提下,会考虑程序的运行时间。我们会用两个不同的输入数据文件(一个简单一个复杂)进行测试,简单的输入数据产生的程序输出结果如果正确,获该题满分的30%即15分(不处理运行时间,除非因程序错误引起的超时运行);复杂的输入数据产生的程序输出结果如果正确,获50%即25分,运行时间满分为20%即10分,按各自程序的运行时间在所有参赛选手的程序的运行时间中所占位置获得相应比例。请仔细阅读并遵守"输入数据"和"输出数据"中的格式要求,如不符合要求,我们的自动评分程序可能会判定程序不正确。

搜索更多相关主题的帖子: 经典 
2005-09-24 16:55
jinmu0755
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2005-9-24
收藏
得分:0 
请高手指教

2005-09-25 21:04
快速回复:[求助]一个关于图的经典问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017972 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved