Блог пользователя sys.

Автор sys., история, 5 лет назад, По-английски

One day when I had my math class,I came up with an idea.But I found that I can't solve it.

After class I asked many people but they did't solve it too.

Here's the problem:

You are given a undirected weighted graph with n nodes and m edges.

You need to find a simple path from 1 to n to maximize the maximum value of edges in the path minus the minimum one.

A simple path means that you can't pass through one edge twice or more.

(I don't know how large n,m can be)

Update:Thanks to TimonKnigge,we can solve it in $$$O(m^2 \times n^3)$$$

  • Проголосовать: нравится
  • +53
  • Проголосовать: не нравится

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

If the problem is minimize the maximum value of edges in the path minus the minimum one.

we can use Link-Cut Tree and two pointer to solve it.

We can sort edges by their value and add it in the Link-Cut Tree.

If there is a loop,we can delete the edge which has the minimum value in the loop.

The complexity is $$$O(mlogm)$$$

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    You can submit this problem (where you minimize the difference) here.

    The constraints allow simpler approaches to get an "Accepted" verdict.

»
5 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

I bet you can solve the problem if N <= 10

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +77 Проголосовать: не нравится

A slow but polynomial solution: let's loop over all $$$O(m^2)$$$ pairs of candidate edges for the minimum and maximum edge. Remove all edges that have smaller or larger weight. Now we want to find a simple path from $$$1$$$ to $$$n$$$ in the remaining graph that uses these two edges. However, this is a relatively straightforward flow problem. We simply set the minimum capacity of these two edges to $$$1$$$ (and the maximum capacity of all edges to $$$1$$$ as well) and find a flow from $$$1$$$ to $$$n$$$. It is pretty easy to see the number of augmenting paths for this problem will be constant, so the complexity is $$$O(m^3)$$$.

  • »
    »
    5 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +23 Проголосовать: не нравится

    I'm sorry maybe you are right.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    Remove all edges that have smaller or larger weight.

    We don't even need this, since we're looking for the maximum difference. That means we can work with a fixed graph, but idk if it improves things.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    $$$\def\set[#1]{\left\{#1\right\}}$$$

    The flow might have some cycles disjoint from the path from $$$1$$$ to $$$n$$$, so you won't necessaritly find a simple path.

    Counterexample

    Instead, loop over all pairs $$$(e_1, e_2)$$$ of edges. A simple path from $$$1$$$ to $$$n$$$ that uses two edges $$$e_1 = \set[u_1, v_1]$$$,$$$ e_2 = \set[u_2, v_2]$$$ looks like

    $$$ 1 -\dots -u_1 -v_1 -\dots -u_2 -v_2 -\dots -n $$$

    up to some permutation of $$$\set[u_1, v_1, u_2, v_2]$$$, so the problem of finding such a path boils down to finding three vertex disjoint paths $$$1 - \dots - u_1, v_1 - \dots - u_2, v_2 - \dots - n$$$. The paper Graph Minors .XIII. The Disjoint Paths Problem gives a (complicated) $$$O(n^3)$$$ algorithm for checking if such paths exist, so we get $$$O(m^2 n^3)$$$ runtime in total.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by sys. (previous revision, new revision, compare).

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think it can be solved faster. Let's do binary search of the answer. Now, we want to check whether we can reach difference less than $$$d$$$. If we fix maximum weight $$$w_{max}$$$ that will present in the path it's easy to see that all available weights of edges from a segment $$$[w_{max}-d, w_{max}]$$$. So we got a solution that works in $$$O(m^2 \cdot log(MAX \underline\ W))$$$.

From the other point of view all edges are available in segment of maximal weights in the path so we can apply dynamic connectivity over the weights, where every edge available in $$$[w, w+d]$$$. We got something about $$$O(m \cdot log(m) \cdot log(MAX \underline\ W))$$$.

Correct me if I'm wrong.

  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    I think it's not right.But still thank you!

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +46 Проголосовать: не нравится

    I think that you are trying to minimize the $$$|w_{max} - w_{min}|$$$. The problem asks that we should maximize the difference.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Say you have a direct edge from $$$1$$$ to $$$n$$$ of some weight $$$w$$$ (amongst other edges). How does your algorithm work in this case?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by sys. (previous revision, new revision, compare).

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by sys. (previous revision, new revision, compare).