Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

Adibov's blog

By Adibov, history, 2 months ago, In English,

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.

 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Actually the problem is equal to longest path when all weights are 1 and Q = 1. So it's np-hard!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you but what if we want that sum of all queries become minimized?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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