Блог пользователя KrK

Timus 1035
Автор KrK, 13 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
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.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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?
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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.
    → Ответить