Gabriel_Duarte

Untitled

May 3rd, 2014
321
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.53 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <float.h>
  5.  
  6. // MST Algoritmo de PRIM
  7.  
  8. #define dist(x, x1, y, y1) sqrt(pow(x - x1, 2) + pow(y - y1, 2))
  9. #define MAX 501
  10.  
  11. double grafo[MAX][MAX];
  12.  
  13. struct dados
  14. {
  15.     int x, y;
  16.        
  17. }pessoas[MAX];
  18.  
  19.  
  20. double prim(int n) // Tamanho
  21. {  
  22.     double fixo[MAX];
  23.     double custo[MAX];
  24.    double total = 0;
  25.  
  26.     for(int i = 0; i < n; i++)
  27.     {
  28.         fixo[i] = 0;
  29.         custo[i] = FLT_MAX; // Ou INF se for Inteiro
  30.     }
  31.     custo[0] = 0;
  32.  
  33.     for(int faltam = n; faltam > 0; faltam--)
  34.     {
  35.         int no = -1;
  36.         for(int i = 0; i < n; i++)
  37.             if(!fixo[i] && (no == -1 || custo[i] < custo[no]))
  38.             no = i;
  39.         fixo[no] = 1;
  40.  
  41.         if(custo[no] == FLT_MAX)
  42.         {
  43.             total = FLT_MAX;
  44.             break;
  45.         }
  46.         total += custo[no];
  47.  
  48.         for(int i = 0; i < n; i++)
  49.             if(grafo[no][i] != -1)
  50.                 if(custo[i] > grafo[no][i])
  51.                 custo[i] = grafo[no][i];
  52.     }
  53.    
  54.     return total;
  55. }
  56.  
  57. int main()
  58. {
  59.     int c, n;
  60.    
  61.     scanf("%d", &c);
  62.     while(c--)
  63.     {
  64.         scanf("%d", &n);
  65.         for(int i = 0; i < n; i++)
  66.            scanf("%d %d", &pessoas[i].x, &pessoas[i].y);
  67.        
  68.         for(int i = 0; i < n; i++)
  69.             memset(grafo[i], 0xff, sizeof(float) * n);
  70.    
  71.         for(int i = 0; i < n - 1; i++)
  72.             for(int j = i + 1; j < n; j++)
  73.                 grafo[i][j] = grafo[j][i] = dist(pessoas[i].x, pessoas[j].x, pessoas[i].y, pessoas[j].y);
  74.                
  75.          
  76.         printf("%.2lf\n", prim(n) / 100.00);  
  77.            
  78.     }
  79.     return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment