• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ1125 – Stockbroker Grapevine

    ACM-POJ EXP 147阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    问题描述

    众所周知,证券经纪业依靠的就是过度的传言。您需要想出股票经纪人中传播假情报的方法,让您的雇主在股票市场的占据优势。为了获得最大的效果,你必须蔓延最快的方式谣言。

    不幸的是你,股票经纪人信息只信任他们的“可靠来源”,这意味着你在你传播谣言之前必须考虑到他们的接触结构。它需要特定股票经纪人和一定的时间把谣言传递给他的每一位同事。你的任务将是写一个程序,告诉您选择哪一个股票经纪人作为谣言的出发点和所花费多少时间将谣言扩散到整个社会的股票经纪人。这一期限是衡量过去的人收到信息所需的时间。

    输入

    你的程序包含多组股票经纪人的输入数据。每组以股票经纪人的人数开始。接下来的几行是每个经纪人与其他人接触的一些信息,包括这些人都是谁,以及将讯息传达到他们所需的时间。每个经纪人与其他人接触信息的格式如下:开头的第一个数表示共有n个联系人,接下来就有n对整数。每对整数列出的第一个数字指的是一个联系人(例如,一个’1’是指编号1的人),其次是在传递一个信息给那个人时所采取分钟的时间。没有特殊的标点符号或空格规则。

    每个人的编号为1至经纪人数目。所花费的传递时间是从1到10分钟(含10分种)。股票经纪的人数范围是从1到100。当输入股票经纪人的人数为0时,程序终止。
    输出

    在对于每一组数据,你的程序必须输出一行,包括的信息有传输速度最快的人,以及在最后一个人收到消息后,所总共使用的时间(整数分钟计算)。

    你的程序可能会收到的一些关系会排除一些人,也就是有些人可能无法访问。如果你的程序检测到这样一个破碎的网络,只需输出消息“disjoint”。请注意,所花费的时间是从A传递消息到B,B传递信息到A不一定是花费同样的传递时间,但此类传播也是可能的。

    解题思路

    最短路问题Floyd算法。相比于Bellman和Dijkstra,我认为是最接近人类自然思维的算法,O(∩_∩)O哈哈~说真的,我第一次做Floyd的题目时,我没有看过Floyd算法,我自己把Floyd推导出来了。。。

    至于数据的存储,就用邻接矩阵,只要对矩阵上的时间进行修改就行了,相对比较方便。

    转载请注明:EXP 技术分享博客 » POJ1125 – Stockbroker Grapevine

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址