TOPIC

100% WA, o que está acontecendo?

Nelson Gomez asked 3 years ago

Meu código passou bonito em outros sites, mas, por algum motivo obscuro, aqui dá WA .-.

Remember not post solutions. Your post may be reviewed by our moderators.

  • Axell Brendow Batista Moreira replied 11 months ago

    Galera, uma forma de resolver esse problema é criar um grafo bipartido onde você tem pedaços de linhas de um lado e pedaços de colunas do outro. Daí você cria uma aresta entre pedaços que podem se atacar. As arestas seriam as torres. Quanto mais arestas for possível pegar sem que duas compartilhem os mesmos vértices, você chega na resposta. Ou seja, é um problema de casamento máximo que pode ser resolvido usando o algoritmo de fluxo máximo (https://www.youtube.com/watch?v=x2BdRml5lmc).

    X....
    X....
    ..X..
    .X...
    ....X
    
    IDs linhas:
    X1111
    X2222
    33X44
    5X666
    7777X
    
    IDs colunas:
    X2467
    X2467
    12X67
    1X567
    1356X