Implémentation de minimum spanning tree pour une société d'autoroutes

Télécharger le projet
Commenter

Description

mon code sert pour trouver le minimum de goudron pour que certaines villes seront connectés entre eux
en faite c'est la resolution d'un probleme dans un concours de programmation (enoncé du probleme dans le ZIP)

Source / Exemple : 


#include<iostream>
#include<queue>
   using namespace std;
           
   struct edge{
           
   
   
      char a,b;
      int d;       
   
   
              
      edge(char a,char b,int d){
              
      
      
         this->a=a;
         this->b=b;
         this->d=d;        
      }
   };

           
   struct compare{
           
              
      bool operator()(edge e1,edge e2){
              
      
         return e1.d>e2.d;   
      }
   };  

           
   int main(){
           
   
      freopen("grand.out","w",stdout);
      freopen("grand.in","r",stdin);      
      int n,distance,n_voisins;     
      char v,v_voisine;
      cin>>n;
      while(n!=0){
         priority_queue<edge,vector<edge>,compare> pQ;
         for(int i=0;i<n-1;i++){           
            cin>>v>>n_voisins;
         
            for(int j=0;j<n_voisins;j++){                        
               cin>>v_voisine>>distance;
               edge e(v,v_voisine,distance);
               pQ.push(e);
            }    
         }       
      
         bool ville[26][26];
         for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
               ville[i][j]=(i==j); 
         int min_distance=0;
      
         while(!pQ.empty()){         
            int v1=pQ.top().a-'A';
            int v2=pQ.top().b-'A';
            int d=pQ.top().d;
            pQ.pop();
            if(!ville[v1][v2])
            { min_distance+=d;              
               for(int i=0;i<n;i++)              
                  for(int j=0;j<n;j++)                  
                     if(ville[i][v1] && ville[v2][j])
                        ville[i][j]=ville[j][i]=true;     
            }                  
         
         
         }
         cout<<min_distance<<endl;
         cin>>n;
         
      }
      return 0;
   
   }

Conclusion :


mon code peut aussi servir pour trouver les villes qui seront connectées entre eux !
il faut simplement afficher la structure des edges .
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (elkasimi2007)