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)$$$
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)$$$
You can submit this problem (where you minimize the difference) here.
The constraints allow simpler approaches to get an "Accepted" verdict.
Ohhhhh!Thank you!
I bet you can solve the problem if N <= 10
............
That's for sure.
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)$$$.
I'm sorry maybe you are right.
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.
$$$\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.
On the graph
the answer is clearly $$$0$$$, as there is exatly one path from $$$1$$$ to $$$5$$$, but $$$1 \to 5, 2 \to 3 \to 4 \to 2$$$ is a flow for the edges $$$1 - 5, 4 - 2$$$ giving you an answer of $$$3$$$.
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
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.
Auto comment: topic has been updated by sys. (previous revision, new revision, compare).
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.
I think it's not right.But still thank you!
I think that you are trying to minimize the $$$|w_{max} - w_{min}|$$$. The problem asks that we should maximize the difference.
Just change the weight segment then it becomes maximization.
Oh.....Maybe you are right.
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?
Auto comment: topic has been updated by sys. (previous revision, new revision, compare).
Auto comment: topic has been updated by sys. (previous revision, new revision, compare).