l*********r
发帖数: 674 | 1 一个无向图，edge有权重(positive int)。找从node A到node B的最小cut（cut on edges, 最小就是说edge的权重的sum最小）。 |
l*********r
发帖数: 674 | 2 这题有什么好的解法么？我当时想了半天，就是先从起点计算它的sum of out edge's
weight, 然后把他指向的neighbor加进去，当成一个super node，然后recursively这
么做。大概思想虽然这样，但是实现挺麻烦，没做完，中间还要考虑重复这些super
node的重复，比如说A+B+C和A+C+B是一样的。
有没有谁能给个好的解法和优化？ |
j*****n
发帖数: 1545 | 3 土问啥叫从 node A到node B的最小cut? 是说找一个cut把A和B分开么? 那就是
Maxflow-mincut吧, |
r****0
发帖数: 20 | 4 IBM不错
edges, 最小就是说edge的权重的sum最小）。
【在 l*********r 的大作中提到】
: 一个无向图，edge有权重(positive int)。找从node A到node B的最小cut（cut on edges, 最小就是说edge的权重的sum最小）。
|
h******3
发帖数: 351 | 5 IBM 问这么多图的问题?
edges, 最小就是说edge的权重的sum最小）。
【在 l*********r 的大作中提到】
: 一个无向图，edge有权重(positive int)。找从node A到node B的最小cut（cut on edges, 最小就是说edge的权重的sum最小）。
|
l*********r
发帖数: 674 | 6 就是说cut几个edge，让A和B之间没有path可以连通。
我对这个领域也不熟，不知道什么是Maxflow-mincut，呵呵。
【在 j*****n 的大作中提到】
: 土问啥叫从 node A到node B的最小cut? 是说找一个cut把A和B分开么? 那就是
: Maxflow-mincut吧,
|
l*********r
发帖数: 674 | 7 还有什么别的图的题么？我好像最近没看到有人问IBM的问题啊？
【在 h******3 的大作中提到】
: IBM 问这么多图的问题?
:
: edges, 最小就是说edge的权重的sum最小）。
|
S**I
发帖数: 15689 | 8 这就是Max-flow Min-cut算法的简单应用。
【在 l*********r 的大作中提到】
: 就是说cut几个edge，让A和B之间没有path可以连通。
: 我对这个领域也不熟，不知道什么是Maxflow-mincut，呵呵。
|
S**I
发帖数: 15689 | 9 常见的图形算法也就是minimum spanning tree, shortest path, maximum flow这几类
了。更复杂的图形算法也有，不过一般不适合面试使用。
【在 l*********r 的大作中提到】
: 还有什么别的图的题么？我好像最近没看到有人问IBM的问题啊？
|
J*********n
发帖数: 370 | 10 可以用最大流做，不过原图是无向的，所以需要把原来的每条边变成两条边，一个方向
一条。 |
