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

Автор akash2504, 12 лет назад, По-английски

http://www.spoj.com/problems/PT07X/ Can someone help me to solve above problem? i m stuck n couldnt find any way through :(

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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Well, it's a pretty easy problem. You should maintain a queue of vertices with degree equal to 1 and add their neighbours to the answer, decrease the neighbour's neighbours' degree by 1 and add those which get degree equal to 1 to the queue.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Its a tree .... so it is bipartite. So maximum matching is the answer. As n = 100000, we can use Hopcroft–Karp Bipartite Matching. I got AC using Bipartite Matching.

  • »
    »
    10 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    I think we don't really need a matching. As you mentioned the graph is bipartite. After running a BFS or DFS the answer is the size of the part with minimum elements.

    Note: I'm not sure about the correctness of my idea. I'm not home and I can't write it now.

    Update: I'm wrong and I'm sorry for confusing you... My code

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

Actually, this is a DP problem. Let DP[i][0] be the cost of solving the subtree rooted at i when i itself is not selected, and DP[i][1] be the cost of solving the subtree rooted at i when i is selected. If we don't select i, we must select all its children, otherwise there will be edges with no selected vertex. If we select i, we can freely choose whether or not to select their children when we solve those subtrees. Then...

In the formulas above, c represents the set of children of node i. The answer we seek will be the minimum of DP[1][0] and DP[1][1], assuming we root our tree at node 1.