Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

fibra otica

By: a guest on May 9th, 2012  |  syntax: C++  |  size: 1.47 KB  |  hits: 20  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. #define MAX_EDGES 150000
  5. #define MAX_NODES 1000
  6.  
  7. using namespace std;
  8.  
  9. struct Edge {
  10.         int u, v, cost;
  11.  
  12.         void set (int x, int y, int custo) {
  13.                 u = x;
  14.                 v = y;
  15.                 cost = custo;
  16.         }
  17.  
  18.         bool operator <(const struct Edge &lhs) const {
  19.                 return cost < lhs.cost;
  20.         }
  21.  
  22.         void imprimir () {
  23.                 printf("%d %d\n", u, v);
  24.         }
  25. };
  26.  
  27. Edge aresta[MAX_EDGES];
  28. int rep[MAX_NODES];
  29. vector <Edge> agpm;
  30.  
  31. int n, m, u, v, c;
  32.  
  33. bool read () {
  34.         scanf("%d %d", &n, &m);
  35.         if(!n) return false;
  36.         for (int i = 1; i <= n; i++) {
  37.                 rep[i] = i;
  38.         }
  39.  
  40.         for (int i = 0; i < m; i++) {
  41.                 scanf("%d %d %d", &u, &v, &c);
  42.                 if (u < v) aresta[i].set(u, v, c);
  43.                 else aresta[i].set(v, u, c);
  44.         }
  45.         return true;
  46. }
  47.  
  48. int find (int pos) {
  49.         if (rep[pos] == pos) return pos;
  50.  
  51.         rep[pos] = find(rep[pos]);
  52.         return rep[pos];
  53. }
  54.  
  55. bool uniao (int a, int b) {
  56.         int temp1 = find(a);
  57.         int temp2 = find(b);
  58.  
  59.         if (temp1 != temp2) {
  60.                 rep[temp1] = temp2;
  61.                 return true;
  62.         }
  63.  
  64.         return false;
  65. }
  66.  
  67. int qtd;
  68.  
  69. void kruskal () {
  70.         sort (aresta, aresta + m);
  71.         for (int i = 0; i < m && qtd < n; i++) {
  72.                 if (uniao(aresta[i].u, aresta[i].v)) {
  73.                         agpm.push_back(aresta[i]);
  74.                         qtd++;
  75.                 }
  76.         }
  77. }
  78. int testes = 1;
  79. void process () {
  80.         qtd = 1;
  81.         printf("Teste %d\n", testes++);
  82.         agpm.clear();
  83.         kruskal();
  84.         for (int i = 0; i < qtd - 1; i++) {
  85.                 agpm[i].imprimir();
  86.         }
  87.         printf("\n");
  88. }
  89.  
  90.  
  91. int main () {
  92.         while (read()) {
  93.                 process();
  94.         }
  95.         return 0;
  96. }
create a new version of this paste RAW Paste Data