数学建模社区-数学中国
标题:
怎么样才能求得要通知的最少人数~！
[打印本页]
作者:
gt93
时间:
2013-5-3 10:47
标题:
怎么样才能求得要通知的最少人数~！
本帖最后由 wangzheng3056 于 2013-7-29 17:09 编辑
* ` h. h3 M) m6 c0 ]
# X4 {1 u6 b" C6 S% H9 Q/ C' {# t
时间：三国时期 ；地点：许昌；人物：曹操，你。
8 u, S" t& x0 T
事件：
9 F' p# M, H. H3 `" j$ }* N1 u
起因：曹操得知许昌城里有n个袁绍的奸细。(他们编号为1到n，奸细间存在着一 种消息传递关系，即若C
[j]=1，表示奸细i能直接把消息传给奸细j)。
, A7 U% y4 g% Q: ^' e# n; c
经过：曹操想发布一个假消息，需要传达给所有奸细。曹操命令你来负责消息的发布。
& n3 h2 D! `1 e9 J
结果：聪明的你把消息传递给了很少的几个奸细，就使所有奸细都得到了这个消息。问：最少传递给几个奸细就能完成任务？
# f* m/ s8 j) f8 V0 ?1 ^
* G& L# @# P e( W! B. ?8 \9 Y5 k* P
Input 第一行为N，第二行至第N+1行为N*N的矩阵（若第I行第J列为1，则奸细I能将消息直接传递给奸细J，若第I行第J列为0，则奸细I不能直接将消息传给J ）
/ N- F( G- p8 c. H* }4 w4 U4 f5 L
Output 你最少要传递的奸细的个数
作者:
wangzheng3056
时间:
2013-7-22 13:41
理论上这是一个图的遍历问题。理论上是不好找的最优解的。可能用到一些线性规划，或者用遗传算法或粒子群算法。具体的的突破还看大家和楼主的努力了~！ 这个算法一旦实现，估计能拿个图灵奖~！
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
