ens-ulm-1

google hashcode 2014 source for team ens-ulm-1
git clone https://a3nm.net/git/ens-ulm-1/
Log | Files | Refs

mc2.cpp (2206B)

      1 #include "../louis/louis.cpp"
      2 #include "../louis/ameliore.cpp"
      3 #include "prune.cpp"
      4 
      5 vector<int> sortie[8];
      6 
      7 int choose(vector<int> sss,vector<bool> eee,int pt){
      8 //  return rand()%(adj[pt].size());
      9   vector<int> p(10,0);
     10   int somme=0;
     11   for(int aaaa=0;aaaa<adj[pt].size();aaaa++){
     12   if(eee[id_arete[make_pair(pt,adj[pt][aaaa])]])p[aaaa]=1;
     13   else p[aaaa]=1000*adj[adj[pt][aaaa]].size()/sss[adj[pt][aaaa]]/distance[id_arete[make_pair(pt,adj[pt][aaaa])]];
     14   //else if(sss[adj[pt][aaaa]])p[aaaa]=200;
     15 //  else p[aaaa]=10000;  
     16   somme+=p[aaaa];
     17     }
     18   int aaaa=rand() % somme;
     19   int target=0;
     20   int cumul=0;
     21 
     22   for(int i=0;i<adj[pt].size();i++){
     23     
     24     if(aaaa >= cumul && aaaa < cumul+p[i]) return i;
     25     
     26     cumul+=p[i];
     27   }
     28 printf("NON\n");  
     29 }
     30 
     31 
     32 
     33 void completion_hasard(int t, int i,vector<int> sss,vector<bool> eee){
     34 
     35 
     36 
     37 
     38   int pt=sortie[i][sortie[i].size()-1];
     39  while(true){
     40 //   int d=rand()%(adj[pt].size());
     41 
     42 int d=choose(sss,eee,pt);
     43 if(d>=adj[pt].size())  printf("NON %d %d\n",d,adj[pt].size());
     44 
     45 //
     46 
     47    int ar=id_arete[make_pair(pt,adj[pt][d])];
     48    if(t+cout[ar]>t_autorise) break;
     49    t+=cout[ar];
     50    eee[ar]=true;
     51    sss[pt]+=1;
     52    sortie[i].push_back(adj[pt][d]);
     53    pt=adj[pt][d];
     54  }
     55   
     56 }
     57 
     58 
     59  
     60 int main(){
     61 srand(time(NULL));
     62 lecture_entree();
     63 init_use();
     64 
     65 
     66 int bsol=0;
     67 vector<int> best_sol[8];
     68 
     69 for(int test=0;test<50;test++){
     70 vector<int> sss(12000,1);
     71 vector<bool> eee(18000,false);
     72 
     73 
     74 for(int i=0;i<n_vehicules;i++){
     75 sortie[i].clear();
     76   int pt=s_depart;
     77   sortie[i].push_back(s_depart);
     78   sortie[i].push_back(8255);
     79   sortie[i].push_back(rand()%n_sommets);
     80   sortie[i]=complete(sortie[i]);
     81   completion_hasard(evalue_solution(sortie).at(i),i,sss,eee);
     82 }
     83 int aaa=score_solution(sortie);
     84 if( aaa > bsol){ for(int i=0;i<n_vehicules;i++)best_sol[i]=sortie[i]; bsol=aaa;fprintf(stderr,"%d\n",aaa);}
     85 
     86 }
     87 
     88 
     89 
     90 
     91 vector<int> sortiesuivante[8];
     92 vector<int> bs2[8];
     93 
     94 
     95 
     96 //affichage de la solution
     97 /*
     98 for(int i=0;i<n_vehicules;i++){
     99  printf("%d\n",bs2[i].size());
    100  for(int j=0;j<bs2[i].size();j++){printf("%d\n",bs2[i][j]);}
    101 }
    102 */
    103 ameliore_louis(bs2);
    104 /*
    105 for(int i=0;i<n_vehicules;i++){
    106  printf("%d\n",best_sol[i].size());
    107  for(int j=0;j<best_sol[i].size();j++){printf("%d\n",best_sol[i][j]);}
    108 }
    109 */
    110 
    111 
    112 
    113 
    114 }
    115