Need help with another graph theory problem

Правка en1, от xuanquang1999, 2017-07-06 17:55:35

In this morning training, our team was given this problem from Prologin contest — 2015 Regional event (unfortunately, the statement is written in French, but I'll try to summarize the statement as accurate as possible):

"There are N rooms and M roads, road i directly connect room ui with room vi. There are also K switches, switch i can control road ai and road bi. More specifically, if switch j is on, roads ai is enabled and roads bi is disabled, and vice-versa (disabled road can't be walked on). If there is no switch controlling road i, then that road is always enabled. It's guaranteed that one road will be controlled by at most one switch, and when all switches are off, the roads system will form a tree (connected acyclic graph). Is it true that for all 2k states of the switches, the roads system will always form a tree?"

Our teams have discussed this problem for the entire morning but failed to come up with any algorithm that can solve this problem in polynomial time. It also doesn't help that the original statement didn't give constraint of N, M, and K, too. Can someone help us on this matter? Thanks in advance.

Теги graph, help needed

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский xuanquang1999 2017-07-06 17:57:13 6
en2 Английский xuanquang1999 2017-07-06 17:56:40 4 Tiny change: 'l road $a_i$ and road $b_i$. More sp' -> 'l road $a_j$ and road $b_j$. More sp'
en1 Английский xuanquang1999 2017-07-06 17:55:35 1295 Initial revision (published)