KrK's blog

Timus 1035
By KrK, 13 years ago, In English

Hello,

Maybe someone has solved this problem. I tried to solve it but everything was in vain. I think that we have a disconnected graph and we just need to count degrees of every vertex in connected components. Then we know what minimum number of threads is needed. But how to create a graph from the given images? One very intuitive approach would be this. Where red edges are stitches on the face of cloth and green edges are stitches on the rear of cloth. The graph itself represents the sample input. How to change this graph that the problem could be solved? I think that we need to make its edges of the same type. But how to do it?

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

13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
You don't need any additional changes to the graph - just think what property every path in this colored graph possesses and how to minimize what you need.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I tried this strategy: for any connected component, for every vertice in it do this: min_paths += out_red + out_green - min(out_red, out_green), then make path from this vertice to neighbours when it is possible in this way: green -> red, red -> green, in fact it works like DFS deleting all used edges.
    I get WA #9 with this. Why doesn't it work? What is the correct approach?
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Oh... I just noticed that my described strategy won't work even for the example case when we select 2;2 as the start vertex in the first connected component. It is certainly not proper.
    → Reply