Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2459
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2459
Copa do Mundo
Por OBI - Olimpíada Brasileira de Informática 2014 
Brazil
Timelimit: 1
A Nlogônia é atualmente um dos países com maior crescimento econômico no mundo, e seus governantes têm se esforçado para que o país seja mais conhecido e respeitado internacionalmente. Recentemente a Nlogônia foi escolhida para ser a sede da Copa do Mundo de Futebol Amador, e está se preparando para receber os milhares de torcedores que o evento atrai.
Como parte da preparação para a Copa, o governo planeja realizar uma reforma em todo o sistema de transporte intermunicipal, que é hoje composto de uma malha de rodovias e ferrovias, cada rodovia ou ferrovia interligando um par de cidades. Com as rodovias e ferrovias existentes já é possível viajar entre qualquer par de cidades (possivelmente passando por outras cidades no caminho), mas o governo quer oferecer melhores condições de transporte para os visitantes e a população.
Como não há recursos para reformar todas as rodovias e ferrovias, o governo quer escolher um conjunto de rodovias e ferrovias para ser reformado, e já realizou um estudo para estabelecer o custo de reforma de cada rodovia e ferrovia. A escolha deve obedecer aos seguintes critérios:
- ao final da reforma, deve ser possível viajar entre qualquer par de cidades (possivelmente passando por outras cidades) utilizando apenas rodovias ou ferrovias reformadas;
- para priorizar o transporte público, dentre as escolhas que satisfazem a restrição 1, deve-se escolher uma que minimize o número de rodovias reformadas;
- dentre as escolhas que satisfazem as restrições 1 e 2, deve-se escolher uma que minimize o custo total.
Você foi contratado para escrever um programa que, conhecidos os custos de reforma de cada rodovia e ferrovia, determine o menor custo possível para a reforma, obedecidos os critérios estabelecidos.
Entrada
A primeira linha da entrada contém três inteiros N (2 ≤ N ≤ 100), F (1 ≤ F ≤ N(N − 1)/2) e R (1 ≤ R ≤ N(N − 1)/2), indicando respectivamente o número de cidades, de ferrovias e de rodovias. As cidades são identificadas por inteiros de 1 a N. Cada uma das F linhas seguintes descreve uma ferrovia e contém três inteiros A, B (1 ≤ A < B ≤ N) e C (1 ≤ C ≤ 1000), onde A e B representam cidades e C representa o custo da reforma da ferrovia que interliga A e B. Cada uma das R linhas seguintes descreve uma rodovia e contém três inteiros I, J e K, onde I e J (1 ≤ I < J ≤ N) representam cidades e K (1 ≤ K ≤ 1000) representa o custo da reforma da rodovia que interliga I e J.
Saída
Seu programa deve produzir uma única linha, contendo o menor custo possível para o conjunto de reformas de ferrovias e rodovias, obedecendo aos critérios estabelecidos.
| Exemplos de Entrada | Exemplos de Saída |
|
3 3 2 1 2 1000 1 3 1000 2 3 900 1 3 800 2 3 700 |
1900 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
using namespace std;
#define MAXN 110
#define MAXM 5000
int pai[MAXN], peso[MAXN], n, f, r, resposta;
pair < int, pair<int, int> > ferrovias[MAXM], rodovias[MAXM];
int find(int x) {
if (x == pai[x]) return x;
return pai[x] = find(pai[x]);
}
void join(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (peso[x] < peso[y])
pai[x] = y;
else if (peso[x] > peso[y])
pai[y] = x;
else {
pai[x] = y;
peso[y]++;
}
}
int main() {
scanf("%d %d %d", &n, &f, &r);
for (int i = 1; i < = n; i++) pai[i] = i;
for (int i = 0; i < f; i++) {
int u, v, peso;
scanf("%d %d %d", &u, &v, &peso);
ferrovias[i] = make_pair(peso, make_pair(u, v));
}
for (int i = 0; i < r; i++) {
int u, v, peso;
scanf("%d %d %d", &u, &v, &peso);
rodovias[i] = make_pair(peso, make_pair(u, v));
}
sort(ferrovias, ferrovias + f);
sort(rodovias, rodovias + r);
for (int i = 0; i < f; i++) {
if (find(ferrovias[i].second.first) !=
find(ferrovias[i].second.second)) {
resposta += ferrovias[i].first;
join(ferrovias[i].second.first, ferrovias[i].second.second);
}
}
for (int i = 0; i < r; i++) {
if (find(rodovias[i].second.first) != find(rodovias[i].second.second)) {
resposta += rodovias[i].first;
join(rodovias[i].second.first, rodovias[i].second.second);
}
}
printf("%d\n", resposta);
return 0;
}
Input
1 2 1000
1 3 1000
2 3 900
1 3 800
2 3 700
Output