MMCUT - Tree cut

no tags 

You are given a tree (a connected, acyclic graph) along with a set of commodities, i.e. pairs of vertices, (s1,t1),...,(sm ,tm) (siti). A multicut is a set of edges that when removed disconnects si from ti for all i. There is a unique path Pu,v between every pair of vertices u,v in a tree, and the max-cost of a multicut S is maxi |SPsi, ti|. You will be given a rooted tree of height 1 and a set of commodities and must return the minimum possible max-cost over all multicuts.


The first line of the input is "N M" (1N, M100000), where N is the number of vertices in the tree and M is the number of commodities. All vertices are numbered 0, ...,N-1, and the root has label N - 1. M lines then follow, where the ith line is "si ti", representing a commodity (si, ti) where siti. Commodities are distinct: neither (si, ti) = (sj, tj) nor (si, ti) = (tj, sj) will hold when ij.


Your output should consist of a single number, the minimum possible max-cost of a multicut, followed by a newline.


10 2
0 5
4 8


Added by:Minilek
Time limit:7.601s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:MIT Individual Contest 2007