Hi, I've encountered this graph problem recently, but I couldn't solve it yet. What do you think about it?
There are N vertices and at most N directed edges. Some vertices don't have any edge connecting itself with some other vertex; some have only one. Every vertex has some value assigned to itself (A_i is the value of ith vertex). We can use any edge to move other vertices from the current vertex. We can use even edges that are incoming, but incoming edges cost 1 point, whereas outgoing edges cost nothing. What is the maximum sum of values of vertices that can be traversed when we start at vertex u with K points?
1 <= N <= 1,000
1 <= K <= 100
1 <= A_i <= 10,000
UPD. Things that I forgot to say:
- The graph might have cycles.
- The value of an edge can be added only once to total sum.
- To be clear: Every vertex has 0 or 1 outgoing edge, but there isn't any limit for incoming edges.
If the graph has some cycle, then the answer is unbounded, since we can infinitely run around that cycle. Otherwise, we can add edges with cost 0 and reverse edges with cost 1, and then solve it with a Dijkstra-like algorithm, where the state is Dn, k, meaning the maximum points we can have if we are at node n with k points available.
Do you have any link for the problem?
Um, sorry. I've forgotten to mention it. The graph might have cycles, but the value of an edge can be added only once to total sum.
It's not on any judge or something. Even though I can send a pdf of it, it's Turkish.
Since it has at most N edges then the graph looks like this :
It has a simple cycle, and every node in that cycle is a tree root.
Now solve the problem for a tree Dp1[x][k] the best way to spend k points in the subtree of x
DP2[x][k] the best way to spend k points and return to x
As for the cycle after calculating the dp of every node you should try either going left or right and keep the answers in a dp[k] the same way
I think it doesn't have to have a cycle. And I also couldn't understand how it's turned into a tree. Can you elaborate?
Just try to draw a few examples and you'll see. A cycle with N nodes requires N edges
I'm sorry I may have been unclear, the cycle I'm talking about doesn't need to be in one direction, just imagine an undirected graph
It doesn`t have to have N edges. It can be less than that.
Also, how do you determine a subtree in a directed graph which might have cycles.
ok first consider the case where you have n-1 edges it's a directed tree ignore the direction of the edges for a little bit and root it somewhere now you can see that you will pay either if you're going up or down, try solving this case first then consider N edges
It seems that we can first find scc using tarjan algorithm, and then the graph become a rooted tree.
Then we can use tree dp here , i think the only trick is the component where u belongs isn't the root of tree, but that is not hard to solve .
When you convert strongly connected components into a single vertex, it doesn't become a tree. It just becomes a DAG.
Oh, sorry.
maybe we can change the direction of all edges, then it becomes a tree.
we can first shrink every cycle to a point.
If we ignore directions of edges, it becomes a forest. But I have 2 questions:
How is dp on tree done?
How can I use the result from tree to get the actual result?
I don't mean ignore the direction of edges. I mean change its direction , so every node has only one or none father, so it's a rooted tree (we can always add edge and a point to make forest become a tree, but when calculate the dp, pay a attention to the "edge").
1. we can take the cycle which u belongs as the root of tree (if a node ), and dp[x][k][0] means the maxsum we can get from the subtree of x if we have k points and finally return to x, dp[x][k][1] similar to dp[x][k][0], but this time we don't return to x;
2.the value of tree node is the sum of the cycle value.(if a node don't belong to any cycle, then the tree node just stand for itself).
My english is poor...
I don't think that tree node represents the sum of values of vertices in the cycle. I think it would represent the result of any vertex in the cycle because result would be the same for every vertex that are in cycle, but that's not what I'm asking. Isn't changing the directions of edges going to effect the result? Also, what is the recurrence relation?
Btw, thank you for your help!