m******p
发帖数: 5393 | 1 一学电路的半路出家找coding的，结果遇到这家花街一公司二面，上去就是写卷子，十页，每页一
道题
这道似乎见过，但翻了翻CLRS无解又due了只好网上submit了，可是心有不甘，估计就会毁在这道
题了
大家都是牛人，有耐心的请指教一下吧，发包子
Given a communication network, n nodes are linked to each other by
wireless links (meaning two nodes that are within some distance, d0 of
each other can communicate with each other thus forming a link).
A centralized controller wishes to learn the quality of all the links in
the network. This can be done by querying any node or any set of nodes
and the corresponding nodes can report the quality of the links incident
on them. The controller can only query nodes in a sequential manner
(i.e., no two nodes can be queried or can report in parallel). It takes
t amount of time to query any node. The controller wishes to obtain the
information on all the links in minimum time.
Provide an O(n3) Big O(n cubed)algorithm by which the controller can effi
ciently choose the smallest set of nodes so as to obtain the quality of
all the links in the network or show that this problem is NP-complete |
