ens-ulm-1

commit be72025727f3b4a16d933af4c10f3e664c3041b6
parent bbdab32dfcd6baac68b3e285a35762ef0248c44b
Author: Jachiet Louis <louis@jachiet.com>
Date:   Sat,  5 Apr 2014 15:10:50 +0200

Merge branch 'master' of gitorious.org:ens-ulm-1/ens-ulm-1

Diffstat:
contest/mc/prune.cpp
 | 
47
+++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 47 insertions(+), 0 deletions(-)
diff --git a/contest/mc/prune.cpp b/contest/mc/prune.cpp
@@ -0,0 +1,47 @@
+#include <cstdio>
+#include <algorithm>
+#include <vector>
+#include <queue>
+using namespace std;
+
+
+// essaie d'identifier et de raccourcir les morceaux inutiles de trajet
+void prune(vector<int> trajectoires[], vector<int> resultat[]) {
+  vector<int> order;
+  for (int i=0; i<8; i++)
+    order.push_back(i);
+  random_shuffle(order.begin(), order.end());
+
+  bool aretes[N_ARETES_MAJ];
+  memset(aretes, 0, sizeof(aretes));
+  
+  for (int i=0; i< n_vehicules; i++) {
+    int skipped_last = 0;
+    // push first point
+    resultat[order[i]].push_back(trajectoires[order[i]][0]);
+    for (int j=0; j< int(trajectoires[order[i]].size() - 1); j++) {
+      pair<int, int> p = make_pair(trajectoires[order[i]][j], trajectoires[order[i]][j+1]);
+      int a = id_arete[p];
+      if (!a) {
+        fprintf(stderr, "ERREUR");
+        return;
+      }
+      if (!aretes[a]) {
+        aretes[a] = 1;
+        // j'ai passe une arete utile de j à j+1, donc je dis j+1
+        resultat[order[i]].push_back(trajectoires[order[i]][j+1]);
+        if (skipped_last) {
+          // je dois dire la précédente aussi
+          resultat[order[i]].push_back(trajectoires[order[i]][j]);
+        }
+        // je n'ai plus rien skip
+        skipped_last = 0;
+      } else {
+        // c'est inutile, donc je ne dis pas j+1
+        // je le note
+        skipped_last = 1;
+      }
+    }
+  }
+}
+