SHARE
TWEET

Prim(R)

a guest Oct 20th, 2019 155 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define MAX_LENGTH_ARC 501501
  5. #define MAX_COUNTR_VERTEX 1003
  6.  
  7. char arc[MAX_LENGTH_ARC];// edges
  8. int number[MAX_LENGTH_ARC];//   number of edges
  9. int last[MAX_COUNTR_VERTEX]; //vertex for MST
  10. char mark[MAX_COUNTR_VERTEX]; //old vertex from all graph
  11. int edge_num_MST[MAX_COUNTR_VERTEX];// result
  12.  
  13. //make "index" from v
  14. int makeIndex(int vert1, int vert2) {
  15.     if (vert1 > vert2) {
  16.         return (vert1 * (vert1 - 1)) / 2 + vert2;
  17.     } else {
  18.         return (vert2 * (vert2 - 1)) / 2 + vert1;
  19.     }
  20. }
  21.  
  22. int prim(int n, int v) {
  23.     char dist[MAX_COUNTR_VERTEX];
  24.     for (int i = 0; i < MAX_COUNTR_VERTEX; i++) {
  25.         dist[i] = 'c';
  26.     }
  27.     for (int i = 0; i < n; i++) {
  28.         last[i] = -2000000;
  29.         dist[i] = 'a';
  30.     }
  31.     int index = 0, k = 0;
  32.  
  33.     dist[v] = '/';
  34.     for (int i = 0; i < n; i++) {
  35.         v = 1002;
  36.         for (int j = 0; j < n; j++) {
  37.             if (mark[j] == '-' && (dist[j] < dist[v])) {
  38.                 v = j;
  39.             }
  40.         }
  41.         mark[v] = '+';
  42.  
  43.         if (last[v] != -2000000) {
  44.             index = makeIndex(v, last[v]);
  45.             edge_num_MST[k] = number[index];
  46.             k++;
  47.         }
  48.  
  49.         for (int j = 0; j < n; j++) {
  50.             index = makeIndex(v, j);
  51.             if (arc[index] != ' ') {
  52.                 if (arc[index] < dist[j]) {
  53.                     dist[j] = arc[index];
  54.                     last[j] = v;
  55.                 }
  56.             }
  57.         }
  58.     }
  59.     return k;
  60. }
  61.  
  62. int main() {
  63.     // initialization
  64.     for (int i = 0; i < MAX_COUNTR_VERTEX; i++) {
  65.         mark[i] = '-';
  66.         last[i] = -2000001;
  67.     }
  68.     for(int i = 0; i < MAX_LENGTH_ARC; i++) {
  69.         arc[i] = 'a';
  70.         number[i] = 2000;
  71.     }
  72.  
  73.     FILE *input = fopen("input.txt", "r");
  74.     FILE *output = fopen("output.txt", "w");
  75.  
  76.     int n, m;
  77.     fscanf(input, "%d\n", &n);
  78.     fscanf(input, "%d\n", &m);
  79.  
  80.     for(int i = 0; i < m; i++) {
  81.         int vert1, vert2, edge, index;
  82.         fscanf(input, "%d %d %d", &vert1, &vert2, &edge);
  83.         index = makeIndex(vert1, vert2);
  84.         arc[index] = edge - 1;//for translate to char
  85.         number[index] = i;
  86.     }
  87.  
  88.     int c = prim(n, 0) + 1;
  89.     // sort result
  90.     for(int i = 0; i < c; i++) {
  91.         for(int j = 0; j < c - 1; j++) {
  92.             if(edge_num_MST[j + 1] < edge_num_MST[j]) {
  93.                 int k = edge_num_MST[j];
  94.                 edge_num_MST[j] = edge_num_MST[j + 1];
  95.                 edge_num_MST[j + 1] = k;
  96.             }
  97.         }
  98.     }
  99.     //print result
  100.     for(int i = 1; i < c; i++) {
  101.         fprintf(output, "%d\n", edge_num_MST[i]);
  102.     }
  103.  
  104.     fclose(input);
  105.     fclose(output);
  106.  
  107.     return 0;
  108. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top