Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

ll931110's blog

By ll931110, 7 years ago, In English,

Link to problem statement (problem D)

For short, in this problem, one is provided the minimal cut matrix T (T(u,v) equals to the minimum cut so that u and v are disconnected), and one needs to find a graph G that satisfies T.

I have solved this problem using the observation: if the solution exists, it must be some sort of spanning trees (it also seems to be the author's solution). However, I have no way to prove my observation. Any hint?

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

6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Just in case someone will find this topic later like I did few minutes ago)

I was solving this contest today. Your observation is correct, you may read about Gomory-Hu tree, for every undirected graph one can construct tree with same minimal cut matrix, as Gomory and Hu proved in 1961.