C   24
visit roadn
Guest on 11th February 2023 01:24:19 AM


  1. #include<stdio.h>
  2. #include<math.h>
  3. int cx[800], cy[800], clinked[800];
  4. int road[800][800], roadn[800];
  5. int erect[800], en, check, mind;
  6. double m[800][800];
  7. void visit(int n){
  8.         int i;
  9.         for(i=0; i<roadn[n]; i++){
  10.                 if(clinked[road[n][i]] == 0){
  11.                         erect[en++] = road[n][i];
  12.                         clinked[road[n][i]] = 1;
  13.                         if(roadn[road[n][i]] != 0)visit(road[n][i]);
  14.                 }
  15.         }
  16.         roadn[n] = 0;
  17. }
  18.  
  19. int main(){
  20.         int n;
  21.         int N, M, i, j, r1, r2, ch, link;
  22.        
  23.         double min;
  24.        
  25.         scanf("%d", &n);
  26.         while(n--){
  27.                 memset(m, 0, sizeof(m));
  28.                 memset(clinked, 0, sizeof(clinked));
  29.                 memset(roadn, 0, sizeof(roadn));
  30.                 scanf("%d", &N);
  31.                 for(i=1; i<=N; i++){
  32.                         scanf("%d %d", &cx[i], &cy[i]);
  33.                 }
  34.                 for(i=1; i<=N; i++){
  35.                         for(j=1; j<=N; j++){
  36.                                 m[i][j] = m[j][i] = sqrt((cx[i]-cx[j])*(cx[i]-cx[j])+(cy[i]-cy[j])*(cy[i]-cy[j]));
  37.                         }
  38.                 }
  39.                 scanf("%d", &M);
  40.                 for(i=0; i<M; i++){
  41.                         scanf("%d %d", &r1, &r2);
  42.                         m[r1][r2] = m[r2][r1] = -1;
  43.                         road[r1][roadn[r1]++] = r2;
  44.                         road[r2][roadn[r2]++] = r1;
  45.                 }
  46.                 erect[0] = en = 1;
  47.                 clinked[1] = 1;
  48.                 ch = 1;
  49.                 while(en < N){
  50.                         min = 99999999;
  51.                         check = 1;
  52.                         for(i=0; i<en; i++){
  53.                                 if(roadn[erect[i]] != 0){
  54.                                         visit(erect[i]);
  55.                                         check = 0;
  56.                                         break;
  57.                                 }else{
  58.                                         for(j=1; j<=N; j++){
  59.                                                 if(clinked[j] == 0){
  60.                                                         if(m[erect[i]][j] < min){
  61.                                                                 min = m[erect[i]][j];
  62.                                                                 mind = j;
  63.                                                                 link = erect[i];
  64.                                                         }
  65.                                                 }
  66.                                         }
  67.                                 }
  68.                                 if(check == 0)break;
  69.                         }
  70.                         if(check == 1){
  71.                                 erect[en++] = mind;
  72.                                 printf("%d %d\n", link, mind);
  73.                                 clinked[mind] = 1;
  74.                                 ch = 0;
  75.                         }
  76.                 }
  77.                 if(ch == 1){
  78.                         puts("No new highways need");
  79.                 }
  80.                 if(n != 0)printf("\n");
  81.         }
  82.  
  83.     getchar();
  84.     return 0;
  85. }
Raw Paste

Login or Register to edit or fork this paste. It's free.