You sleep while we work: due to technical reasons Codeforces may be unavailable on May 22 on time interval 01:00-03:00 (MSK). ×

An interesting question

Revision en2, by Adibov, 2018-10-24 14:11:59

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Adibov 2018-10-24 14:11:59 63
en1 English Adibov 2018-10-11 22:40:58 543 Initial revision (published)