I was thinking on a problem and i figure out an interesting problem that i can't solve it so could you help me?
We have an undirected weighted graph and Q queries. Each query has two vertices u and v. For each query erase all of edges between one of the path from v to u, so that sum of all weight of edges that has been erased from all queries become maximized.
I have no idea about time complexity, so there is no limit for n and Q. And if you have seen this problem before please give me the URL.
Thanks. :)
UPD : We want that sum of all queries become minimized.
Actually the problem is equal to longest path when all weights are 1 and Q = 1. So it's np-hard!
Thank you but what if we want that sum of all queries become minimized?
That can be solved with min-cost flow.
Add two new nodes, a source and a sink. Set cost of all edges to 1, then add edges from source to startpoints of the queries, and add edges from endpoints of the queries to the sink. Then minimize cost when pushing Q units of flow.
I doubt there's anything much faster than this.
And what is time complexity?
Auto comment: topic has been updated by Adibov (previous revision, new revision, compare).