ens-ulm-1

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

eu.cpp (3576B)

      1 
      2 #include "../louis/louis.cpp"
      3 #include "../mc/prune.cpp"
      4 
      5 int vu[N_ARETES_MAJ];
      6 vector<int> tps;
      7 
      8 vector<int> cycleAmeliorant(int v, int cur, int dest, int delta, bool first) {
      9   //  fprintf(stderr, "ca %d %d %d\n", v, cur, dest);
     10   if (delta < 0)
     11     return vector<int>();
     12   if (!first && cur == dest)
     13     return vector<int>(1, dest);
     14   int bestArete = -1;
     15   int bestVoisin = -1;
     16   double best = -1;
     17   for (int i = 0; i < int(adj[cur].size()); i++) {
     18     int voisin = adj[cur][i];
     19     int arete = id_arete[make_pair(cur, voisin)];
     20     if (tps[v+1]+cout[arete]>t_autorise)
     21       continue;
     22     double c = double(longueur[arete]) / cout[arete];
     23     if (vu[arete])
     24       c /= 2;
     25     if (c > best) {
     26       bestArete = arete;
     27       bestVoisin = voisin;
     28       best = c;
     29     }
     30   }
     31   if (bestArete >= 0) {
     32     if (vu[bestArete])
     33       delta -= cout[bestArete];
     34     else
     35       tps[0] += longueur[bestArete];
     36     vu[bestArete]++;
     37     tps[v+1] += cout[bestArete];
     38     vector<int> res = cycleAmeliorant(v, bestVoisin, dest, delta, false);
     39     if (!res.empty()) {
     40       res.push_back(bestVoisin);
     41       return res;
     42     }
     43     if (!--vu[bestArete])
     44       tps[0] -= longueur[bestArete];
     45     tps[v+1] -= cout[bestArete];
     46   }
     47   //  return vector<int>(1, dest);
     48   return vector<int>();
     49 }
     50 
     51 bool chercheCycleAmeliorant(vector<int> sol[], int v, int i, int delta) {
     52 
     53   //fprintf(stderr, "Cherche un cycle améliorant pour voiture %d, position %d\n", v, i);
     54 
     55   int score = tps[0];
     56 
     57   vector<int> ca = cycleAmeliorant(v, sol[v][i], sol[v][i], delta, true);
     58 
     59   if (ca.empty())
     60     return false;
     61 
     62   /*  if (score <= tps[0])
     63       return false;*/
     64 
     65   if (score == tps[0])
     66     return false;
     67 
     68   fprintf(stderr, "Trouvé cycle améliorant pour voiture %d, position %d (%d), longueur %d\n", v, i, sol[v][i], int(ca.size()));
     69 
     70   sol[v].insert(sol[v].begin()+i-1, ca.rbegin(), ca.rend());
     71 
     72   sol[v] = complete(sol[v]);
     73 
     74   return true;
     75 }
     76 
     77 void euler(vector<int> sol[]) {
     78 
     79   tps = evalue_solution(sol);
     80 
     81   for (int v = 0; v < n_vehicules; v++) {
     82     for (int i = 0; i < int(sol[v].size() - 1); i++) {
     83       vu[id_arete[make_pair(sol[v][i], sol[v][i+1])]]++;
     84     }
     85   }
     86 
     87   for (int v = 0; v < n_vehicules; v++) {
     88     while (1) {
     89       int cur = sol[v].back();
     90       int bestArete = -1;
     91       int bestVoisin = -1;
     92       double best = -1;
     93       // sel voisin
     94       for (int i = 0; i < int(adj[cur].size()); i++) {
     95         int voisin = adj[cur][i];
     96         int arete = id_arete[make_pair(cur, voisin)];
     97         if (vu[arete])
     98           continue;
     99         if (tps[v+1] + cout[arete] > t_autorise)
    100           continue;
    101         double c = double(longueur[arete]) / cout[arete];
    102         if (c > best) {
    103           bestArete = arete;
    104           bestVoisin = voisin;
    105           best = c;
    106         }
    107       }
    108       if (bestArete < 0)
    109         break;
    110       fprintf(stderr, "La voiture %d continue vers %d\n", v, bestVoisin);
    111       sol[v].push_back(bestVoisin);
    112       vu[bestArete]++;
    113       tps[v+1] += cout[bestArete];
    114       tps[0] += longueur[bestArete];
    115     }
    116     int delta = 0;
    117     while (delta < 424242) {
    118       fprintf(stderr, "Delta %d, score %d\n", delta, tps[0]);
    119       int i = sol[v].size() - 1;
    120       for (; i >= 0; i--) {
    121         if (chercheCycleAmeliorant(sol, v, i, delta))
    122           break;
    123       }
    124       if (i < 0) {
    125         delta = delta*2+1;
    126         continue;
    127       }
    128     }
    129   }
    130 
    131 }
    132 
    133 int main() {
    134   lecture_entree();
    135   init_use();
    136   init_solution(_solution);
    137   goto_etoile2(_solution);
    138   for (int i = 0; i< n_vehicules;i++)
    139     _solution[i] = complete(_solution[i]);
    140   euler(_solution);
    141   affiche_sortie(_solution);
    142 }