ens-ulm-1

lecture.cpp (5725B)

---

 #include <ctime>
 #include <vector>
 #include <map>
 #include <algorithm>
 #include <cstdio>
 #include <cstring>
 #include <cmath>
 
 const int N_SOMMETS_MAJ = 12000;
 const int N_ARETES_MAJ = 18000;
 const int N_DEGRE_MAJ = 6;
 
 using namespace std;
 
  int n_sommets;
  int n_aretes;
  int t_autorise;
  int n_vehicules;
  int s_depart;
 // 8255; //ulm
 double longitude_min, longitude_max;
 double latitude_min, latitude_max;
 double longitude[N_SOMMETS_MAJ];
 double latitude[N_SOMMETS_MAJ];
 
 // caracteristiques d'une arete
 int depart[N_ARETES_MAJ];//depart
 int arrivee[N_ARETES_MAJ];//arrivee
 bool dbsens[N_ARETES_MAJ];//rue a double sens
 int cout[N_ARETES_MAJ];//cout(temps)
 int longueur[N_ARETES_MAJ];//longueur
 
 vector<vector<int> > adj(N_SOMMETS_MAJ); // matrice d'adjacence
 
 map<pair<int, int>, int> id_arete;
 
 vector<int> _solution[8];
 
 void affiche_sortie(vector<int> trajectoires[], FILE *fp) {
   fprintf(fp, "%d\n", n_vehicules);
   for (int i=0; i< n_vehicules; i++) {
     fprintf(fp, "%d\n", (int) trajectoires[i].size());
     for (unsigned int j=0; j<trajectoires[i].size(); j++) {
       fprintf(fp, "%d\n", trajectoires[i][j]);
     }
   }
 }
 
 void affiche_sortie(vector<int> trajectoires[]) {
   affiche_sortie(trajectoires, stdout);
 }
 
 void affiche_sortie(vector<int> sol[], char *filename) {
   FILE *fp = fopen(filename, "w");
   affiche_sortie(sol, fp);
   fclose(fp);
 }
 
 // (temps_tronques)
 // format: score, temps1, temps2, ..., temps8
 // (ou vide si solution invalide)
 vector<int> evalue_solution(vector<int> trajectoires[]) {
   bitset<N_ARETES_MAJ> aretes;
   vector<int> resultat;
   resultat.push_back(0);
   
   int score = 0;
   for (int i=0; i< n_vehicules; i++) {
     int temps = 0;
     for (int j=0; j< int(trajectoires[i].size() - 1); j++) {
       pair<int, int> p = make_pair(trajectoires[i][j], trajectoires[i][j+1]);
       int a = id_arete[p];
       if (!a) {
 	fprintf(stderr,"ERREUR ! %d %d [%d -> %d]",i,j,trajectoires[i][j], trajectoires[i][j+1]);
         resultat.clear();
         return resultat;
       }
       temps += cout[a];
       if (temps >= t_autorise) {
         // undo
         temps -= cout[a];
         break;
       }
       if (!aretes[a]) {
         score += longueur[a];
         aretes[a] = 1;
       }
     }
     resultat.push_back(temps);
   }
   resultat[0] = score;
   return resultat;
 }
 
 int score_solution(vector<int> trajectoires[]) {
   vector<int> v = evalue_solution(trajectoires);
   return v[0];
 }
 
 // in-place truncation to a maximum
 // return 0 unless invalid edge
 int tronque_solution(vector<int> trajectoires[], int max_limit) {
   for (int i=0; i< n_vehicules; i++) {
     int temps = 0;
     for (int j=0; j< int(trajectoires[i].size() - 1); j++) {
       pair<int, int> p = make_pair(trajectoires[i][j], trajectoires[i][j+1]);
       int a = id_arete[p];
       if (!a) {
         return -1;
       }
       temps += cout[a];
       if (temps > max_limit) {
         // j'ai deborde, je cesse la
         trajectoires[i].resize(j);
         break;
       }
     }
   }
   return 0;
 }
 int tronque_solution(vector<int> trajectoires[]) {
   return tronque_solution(trajectoires, t_autorise);
 }
 
 
 void lecture_entree(){
   scanf("%d",&n_sommets);
   scanf("%d",&n_aretes);
   scanf("%d",&t_autorise);
   scanf("%d",&n_vehicules);
   scanf("%d",&s_depart);
   for(int i=0;i<n_sommets;i++) {
     scanf("%lf %lf",&longitude[i],&latitude[i]);
   }
   longitude_min = *min_element(longitude, longitude + n_sommets);
   longitude_max = *max_element(longitude, longitude + n_sommets);
   latitude_min = *min_element(latitude, latitude + n_sommets);
   latitude_max = *max_element(latitude, latitude + n_sommets);
   for(int i=1;i<=n_aretes;i++){
     int x;
     scanf("%d %d %d %d %d",&depart[i],&arrivee[i],&x,&cout[i],&longueur[i]);
     dbsens[i]=(x==2);
     adj[depart[i]].push_back(arrivee[i]); 
     id_arete[make_pair(depart[i], arrivee[i])] = i;
     if(dbsens[i]) {
       adj[arrivee[i]].push_back(depart[i]);
       id_arete[make_pair(arrivee[i], depart[i])] = i;
     }
   }
 }
 
 int plus_proche(double x, double y) {
 
   int iBest = 0;
   double best = hypot(x - longitude[0], y - latitude[0]);
 
   for (int i = 1; i < n_sommets; i++) {
     double cur = hypot(x - longitude[i], y - latitude[i]);
     if (cur < best) {
       best = cur;
       iBest = i;
     }
   }
 
   return iBest;
 }
 
 int plus_proche_norm(double dx, double dy) {
 
   return plus_proche(longitude_min + dx * (longitude_max - longitude_min),
                      latitude_min + dy * (latitude_max - latitude_min));
 
 }
 
 void init_solution(vector<int> sol[]) {
 
   for (int i = 0; i < n_vehicules; i++)
     sol[i].push_back(s_depart);
 
 }
 void goto_etoile2(vector<int> sol[]) {
 
   for (int i = 0; i < n_vehicules; i++) {
     double x = .4 * (1+cos(2*i*M_PI/n_vehicules));
     double y = .4 * (1+sin(2*i*M_PI/n_vehicules));
     int p = plus_proche_norm(x, y);
     sol[i].push_back(p);
     fprintf(stderr, "Etoile2 %d: %lf, %lf -> %d (%lf, %lf)\n", i, x, y, p, longitude[p], latitude[p]);
   }
 
 }
 
 void goto_etoile(vector<int> sol[]) {
 
   for (int i = 0; i < n_vehicules; i++) {
     double x = .5 * (1+cos(2*i*M_PI/n_vehicules));
     double y = .5 * (1+sin(2*i*M_PI/n_vehicules));
     int p = plus_proche_norm(x, y);
     sol[i].push_back(p);
     fprintf(stderr, "Etoile %d: %lf, %lf -> %d (%lf, %lf)\n", i, x, y, p, longitude[p], latitude[p]);
   }
 
 }
 
 void lire_solution(const char *filename, vector<int> sol[]) {
   FILE *fp = fopen(filename, "r");
   if (!fp) {
     fprintf(stderr, "Vérifie '%s'\n", filename);
     exit(1);
   }
   int n_veh;
   fscanf(fp, "%d", &n_veh);
   for (int v = 0; v < n_veh; v++) {
     int size;
     fscanf(fp, "%d", &size);
     for (int i = 0; i < size; i++) {
       int n;
       fscanf(fp, "%d", &n);
       sol[v].push_back(n);
     }
   }
   fclose(fp);
 }