Solução Rede Ótica

Solução por Lucca Siaudzionis

Este problema é uma aplicação direta do algoritmo de encontrar a Árvore Geradora Mínima (clique aqui e confira a aula do Noic sobre isso).

O código, então, fica:


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXL 10010
#define MAXN 110
typedef struct{
int x;
int y;
int peso;
}tipo_aresta;
int crescente(const void *x, const void *y){
if( ((tipo_aresta*)x)->peso > ((tipo_aresta*)y)->peso) return 1;
if( ((tipo_aresta*)x)->peso < ((tipo_aresta*)y)->peso) return -1;
return 0;
}
int main(){
int n,l,teste=1;
while(scanf("%d %d",&n,&l) > 0 && n>0 && l>0){
int cor[MAXN];
tipo_aresta ligacao[MAXL];
int grafo[MAXN][MAXN];
for(int i = 1;i<=n;i++) cor[i] = i;
for(int i=0;i<l;i++) scanf("%d %d %d",&ligacao[i].x,&ligacao[i].y,&ligacao[i].peso);
qsort(ligacao,l,sizeof(tipo_aresta),crescente);
memset(grafo,0,sizeof(grafo));
for(int i=0;i<l;i++){
if( cor[ligacao[i].x] != cor[ligacao[i].y] ){
grafo[ligacao[i].x][ligacao[i].y] = grafo[ligacao[i].y][ligacao[i].x]=ligacao[i].peso;
int aux=cor[ligacao[i].y];
for(int j=1;j<=n;j++) if(cor[j]==aux) cor[j]=cor[ligacao[i].x];
}
}
printf("Teste %d\n",teste++);
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
if(i<j && grafo[i][j]) printf("%d %d\n",i,j);
printf("\n");
}
return 0;
}

view raw

rede_otica.cpp

hosted with ❤ by GitHub