Page Hopping - UVA 821

Em um ambiente com N salas interconectadas (1≤N≤100), calculamos a distância média dos caminhos mais curtos entre todos os pares de salas alcençáveis. A entrada consiste em múltiplos casos de teste terminados com "0 0". Para cada caso, pares de inteiros indicam conexões diretas entre salas.

#include <iostream>
#include <climits>
#include <iomanip>
using namespace std;

const int LIMITE = 101, INF = INT_MAX;

int matriz[LIMITE][LIMITE];
int maiorID;

void preencherMatriz() {
    for(int i = 1; i <= maiorID; i++) {
        for(int j = 1; j <= maiorID; j++) {
            matriz[i][j] = (i == j) ? 0 : INF;
        }
    }
}

void executarFloyd() {
    for(int k = 1; k <= maiorID; k++) {
        for(int i = 1; i <= maiorID; i++) {
            if(matriz[i][k] == INF) continue;
            for(int j = 1; j <= maiorID; j++) {
                if(matriz[k][j] != INF) {
                    matriz[i][j] = min(matriz[i][j], matriz[i][k] + matriz[k][j]);
                }
            }
        }
    }
}

int main() {
    int origem, destino, caso = 1;
    cout << fixed << setprecision(3);
    
    while(cin >> origem >> destino, origem || destino) {
        maiorID = 0;
        preencherMatriz();
        
        do {
            maiorID = max(maiorID, max(origem, destino));
            matriz[origem][destino] = 1;
        } while(cin >> origem >> destino, origem || destino);
        
        executarFloyd();
        double soma = 0;
        int conexoes = 0;
        
        for(int i = 1; i <= maiorID; i++) {
            for(int j = 1; j <= maiorID; j++) {
                if(i != j && matriz[i][j] != INF) {
                    soma += matriz[i][j];
                    conexoes++;
                }
            }
        }
        cout << "Caso " << caso++ << ": comprimento médio = " << soma/conexoes << " cliques\n";
    }
    return 0;
}

Audiophobia

Determinamos a intensidade sonora mínima máxima necessária para percorrer caminhos entre pares de pontos em um grafo. Cada consulta requer encontrar o menor valor máximo de arestas em qualquer caminho entre dois nós.

#include <iostream>
#include <algorithm>
using namespace std;

const int TAM = 101, LIM = 0x3f3f3f3f;

int grafo[TAM][TAM];
int vertices, arestas, consultas;

void configurarGrafo() {
    for(int i = 1; i <= vertices; i++) {
        fill(grafo[i], grafo[i] + vertices + 1, LIM);
        grafo[i][i] = 0;
    }
}

void processarCaminhos() {
    for(int k = 1; k <= vertices; k++) {
        for(int i = 1; i <= vertices; i++) {
            for(int j = 1; j <= vertices; j++) {
                grafo[i][j] = min(grafo[i][j], max(grafo[i][k], grafo[k][j]));
            }
        }
    }
}

int main() {
    int teste = 1;
    while(cin >> vertices >> arestas >> consultas, vertices) {
        configurarGrafo();
        while(arestas--) {
            int a, b, decibeis;
            cin >> a >> b >> decibeis;
            grafo[a][b] = grafo[b][a] = min(grafo[a][b], decibeis);
        }
        processarCaminhos();
        if(teste > 1) cout << "\n";
        cout << "Caso #" << teste++ << "\n";
        while(consultas--) {
            int partida, chegada;
            cin >> partida >> chegada;
            if(grafo[partida][chegada] == LIM) {
                cout << "sem caminho\n";
            } else {
                cout << grafo[partida][chegada] << "\n";
            }
        }
    }
}

As Pontes de Caocao

Identificamos a ponte crítica de menor peso em uma rede de ilhas. A remoção dessa ponte desconecta o grafo, com restrições especiais para pesos zero ou ausência de soluções.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_NOS = 1010, MAX_ARESTAS = 2000010, INF = 0x3f3f3f3f;

int listaAdj[MAX_NOS], prox[MAX_ARESTAS], alvo[MAX_ARESTAS], peso[MAX_ARESTAS];
int registro[MAX_NOS], baixo[MAX_NOS];
int contador, tempo, melhor;
bool ponte[MAX_ARESTAS];

void inicializar(int nos) {
    memset(listaAdj, -1, sizeof(int) * (nos + 1));
    memset(registro, 0, sizeof(int) * (nos + 1));
    contador = tempo = 0;
    melhor = INF;
}

void adicionarAresta(int a, int b, int w) {
    alvo[contador] = b;
    peso[contador] = w;
    prox[contador] = listaAdj[a];
    listaAdj[a] = contador++;
}

void tarjan(int no, int arestaAnterior) {
    registro[no] = baixo[no] = ++tempo;
    for(int i = listaAdj[no]; ~i; i = prox[i]) {
        int viz = alvo[i];
        if(!registro[viz]) {
            tarjan(viz, i ^ 1);
            baixo[no] = min(baixo[no], baixo[viz]);
            if(baixo[viz] > registro[no]) {
                melhor = min(melhor, peso[i]);
            }
        } else if(i != arestaAnterior) {
            baixo[no] = min(baixo[no], registro[viz]);
        }
    }
}

int main() {
    int totalIlhas, totalPontes;
    while(cin >> totalIlhas >> totalPontes, totalIlhas) {
        inicializar(totalIlhas);
        while(totalPontes--) {
            int u, v, guardas;
            cin >> u >> v >> guardas;
            adicionarAresta(u, v, guardas);
            adicionarAresta(v, u, guardas);
        }
        int componentes = 0;
        for(int i = 1; i <= totalIlhas; i++) {
            if(!registro[i]) {
                tarjan(i, -1);
                componentes++;
            }
        }
        if(componentes > 1) {
            cout << "0\n";
        } else if(melhor == INF) {
            cout << "-1\n";
        } else if(melhor == 0) {
            cout << "1\n";
        } else {
            cout << melhor << "\n";
        }
    }
}