Autor da análise: 
tmadeira
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:
- A soma dos vértices da esquerda e do vértices da direita é igual;
- 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]]
Discuta o problema
A complexidade está certa? Acho que, na sua notação, seria $O(N. M^2)$, já que você tem que verificar todos os "pares" de (0, 0) até (M, M).
Tem razão, vou arrumar. Obrigado.