Análisis de Juego en Árbol mediante Minimax

Este problema plantea un escenario de teoría de juegos sobre una estructura de árbol. Dos jugadores se desplazan desde la raíz hacia las hojas, recolectando valores en cada nodo. Dado que ambos juegan de forma óptima, el objetivo es determinar el resultado final (victoria, derrota o empate) para el primer jugador.

Para resolverlo, empleamos un algoritmo de búsqueda en profundidad (DFS) combinado con la lógica de Minimax. En cada nivel del árbol, el jugador actual elegirá el hijo que maximice su beneficio o minimice el del oponente. El estado se propaga desde las hojas hacia la raíz:

• En los nodos hoja, se comparan las puntuaciones acumuladas.
• En los nodos intermedios, si es el turno del primer jugador, seleccionará la rama con el mejor resultado posible.
• Si es el turno del segundo jugador, seleccionará la rama que resulte en el peor esceanrio para el primero.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 100005;
int valores[MAX_N];
vector<int> adj[MAX_N];
long long puntos[2];

// Retorna: 2 para victoria, 1 para empate, 0 para derrota
int evaluar_juego(int u, int p, bool turno_jugador1) {
    bool es_hoja = true;
    int resultado_final = -1;

    int id_jugador = turno_jugador1 ? 0 : 1;
    puntos[id_jugador] += valores[u];

    for (int v : adj[u]) {
        if (v == p) continue;
        es_hoja = false;
        
        int res = evaluar_juego(v, u, !turno_jugador1);
        
        if (resultado_final == -1) {
            resultado_final = res;
        } else {
            if (turno_jugador1) {
                resultado_final = max(resultado_final, res);
            } else {
                resultado_final = min(resultado_final, res);
            }
        }
    }

    if (es_hoja) {
        if (puntos[0] > puntos[1]) resultado_final = 2;
        else if (puntos[0] == puntos[1]) resultado_final = 1;
        else resultado_final = 0;
    }

    puntos[id_jugador] -= valores[u];
    return resultado_final;
}

void resolver() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> valores[i];
        adj[i].clear();
    }
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    puntos[0] = puntos[1] = 0;
    int ans = evaluar_juego(1, -1, true);

    if (ans == 2) cout << "win" << endl;
    else if (ans == 1) cout << "draw" << endl;
    else cout << "loss" << endl;
}

int main() {
    int t;
    if (!(cin >> t)) return 0;
    while (t--) {
        resolver();
    }
    return 0;
}

Diseño de Red Inalámbrica con Árbol de Expansión Mínima (MST)

El problema requiere conectar múltiples puestos fronterizos con el costo mínimo, representado por la distancia de transmisión D. Disponemos de dos tecnologías: radiofrecuencia (con límite de distancia) y teléfonos satelitales (distancia ilimitada).

La estrategia óptima consiste en modelar los puestos como nodos de un grafo completo donde el peso de las aristas es la distancia euclidiana. Al aplicar el Algoritmo de Kruskal para encontrar el Árbol de Expensión Mínima, obtenemos las conexiones más cortas necesarias para unir todos los puntos. Dado que contamos con S teléfonos satelitales, estos pueden sustituir las S-1 aristas más costosas del MST. Por lo tanto, la distancia D necesaria será el peso de la arista número (P-S) en el orden de construcción del MST.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

struct Punto {
    int x, y;
};

struct Conexion {
    int u, v;
    double costo;
    bool operator<(const Conexion& otra) const {
        return costo < otra.costo;
    }
};

int padre[505];

int buscar_padre(int i) {
    if (padre[i] == i) return i;
    return padre[i] = buscar_padre(padre[i]);
}

void unir_nodos(int a, int b) {
    int raiz_a = buscar_padre(a);
    int raiz_b = buscar_padre(b);
    if (raiz_a != raiz_b) padre[raiz_b] = raiz_a;
}

double calcular_distancia(Punto p1, Punto p2) {
    return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
}

int main() {
    int s, p;
    while (cin >> s >> p) {
        vector<Punto> puestos(p);
        vector<Conexion> aristas;

        for (int i = 0; i < p; i++) {
            cin >> puestos[i].x >> puestos[i].y;
            padre[i] = i;
        }

        for (int i = 0; i < p; i++) {
            for (int j = i + 1; j < p; j++) {
                aristas.push_back({i, j, calcular_distancia(puestos[i], puestos[j])});
            }
        }

        sort(aristas.begin(), aristas.end());

        int conexiones_realizadas = 0;
        double distancia_minima = 0;

        for (const auto& arista : aristas) {
            if (buscar_padre(arista.u) != buscar_padre(arista.v)) {
                unir_nodos(arista.u, arista.v);
                conexiones_realizadas++;
                distancia_minima = arista.costo;
                
                // Si tenemos S satélites, solo necesitamos P-S aristas terrestres
                if (conexiones_realizadas == p - s) {
                    cout << fixed << setprecision(2) << distancia_minima << endl;
                    break;
                }
            }
        }
    }
    return 0;
}

Construcción de Grafos de Tipo Cactus

Un grafo cactus es una estructura donde cada arista pertenece a lo sumo a un ciclo simple. El problema de determinar cuántas formas existen de añadir aristas a un grafo para que siga siendo un cactus es un reto de combinatoria y teoría de grafos avanzado. Este tipo de problemas suele resolverse mediante programación dinámica sobre los componentes biconexos del grafo, analizando las restricciones de formación de ciclos para asegurar que no se solapen.