PKU 1636 - Prison rearrangement

Autor da análise: tmadeiratmadeira

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1636

Resumo

Dado um grafo bipartido de $n \leq 200$ vértices de cada lado, determinar o maior número de vértices $\leq \frac{n}{2}$ que posso mudar de lado sem que elementos com uma aresta entre eles fiquem do mesmo lado.

Solução

Usando uma busca em profundidade, encontramos todas as componentes conexas do grafo e as registramos num vetor de pares (o primeiro valor é o número de elementos a esquerda nessa componente e o segundo valor é o número de elementos a direita nessa componente)

Então nosso problema se resume a encontrar o maior subconjunto desses pares que satisfaça:

  1. A soma dos vértices da esquerda e do vértices da direita é igual;
  2. Esta soma é menor ou igual a metade de $n$ (número de vértices total de um lado).

É fácil ver que este é o clássico problema da partição, que pode ser resolvido em $O(NM^2)$ onde $N$ é o número de elementos do conjunto de pares (que é sempre menor que $400$ neste problema) e $M$ é o valor máximo que podemos somar (que é sempre menor que $100$ neste problema).

Após resolver o problema da partição, basta iterar de $n/2$ até $0$ e parar assim que encontrar um valor que é possível atingir.

Testes

Entrada

3
101 0
3 3
1 2
1 3
1 1
8 12
1 1
1 2
1 3
1 4
2 5
3 5
4 5
5 5
6 6
7 6
8 7
8 8

Saída

50
0
3

[[/code]]

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License