问题详细信息:
拉什夫是EMLand的市长。EMLand由交叉口和街道组成。从每个交叉口到其他任何一个交叉口都有一条路径。交叉口用正整数1.n表示。一家建筑公司提供拉什夫来重建EMLand的所有街道,但拉什夫可以选择at most k of them to be rebuilt.。建筑公司为每条街道提供了一个新的长度,这意味着在重建街道后,街道的长度发生了变化。现在,拉什夫作为这座城市的市长,必须做出明智的选择,以便将所有交叉路口之间的路径长度之和降到最低。救救拉什夫!
算法:
标注:旧边长度为L,新长度为L',边集为E。
长度将减少的edges(E')的计数(edges(
注:不需要正式的证明或任何东西,只是算法的一般思想,我会深入研究。
给定一个有向图:G(V,E),我希望找到最小顶点集T,这样对于T中的每个顶点t,都不存在以下边:{(t,v) | for every v outside t} in O(V+E)
换句话说,允许t从T以外的顶点获取边,但不允许发送。
(你可以把它演示为电话,它允许我从外面打电话,它是免费的,但它不允许从我身边打电话给他们)
我认为这个问题非常接近或类似于在有向图中找到所有强连通分量(scc),它的时间复杂度是O(V+E),我正在考虑构建一个新的图并运行这个算法,但不完全确定。
问题:
给出N个节点和M个边的有向图(M,<=,2.N)。查找从所有其他节点可以到达的所有节点。
示例:
下图有4个节点和4个边:
答案:节点(2)和(3)可以从所有其他节点到达。
P/S:
我想出的唯一解决方案是还原图、BFS所有节点并检查它们是否到达所有其他节点。但它需要O(n^2)。
还有其他的方法需要O(n.logn)或更少吗?
下面是我对O(n^2)方法的看法:
void init(){
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v; cin >
我最近在一次采访中遇到了这个问题:
列示矩阵如下:
[[ R R R R R R],
[ R B B B R R],
[ B R R R B B],
[ R B R R R R]]
找出在四个方向上,是否只有R或B的任何一组被相反的颜色包围:上、下、左、右角。
例:回答上面的矩阵,->,B的有效集合,在第二行被R包围。
[[ R R R R R R],
[ R **B B B** R R],
[ B R R R B B],
[ R B R R R R]]
我试着在各个方向上做一个特定颜色的BFS,但是无法解决问题。有人能帮我找到解决方案吗。