commit b63726e7909eac79b536506b693166288ec9dc4d
parent 10de332344b9bab5e85c7abad3c6bc8b0f23123a
Author: Marc Jeanmougin <marc@jeanmougin.fr>
Date: Tue, 8 Apr 2014 23:58:44 +0200
Merge branch 'master' of ssh://gitorious.org/ens-ulm-1/ens-ulm-1
Diffstat:
2 files changed, 128 insertions(+), 6 deletions(-)
diff --git a/contest/louis/louis.cpp b/contest/louis/louis.cpp
@@ -120,6 +120,26 @@ int go_to( int depart, int arrivee)
return use[depart][arrivee] ;
}
*/
+
+ // Comme complete, mais préserve les arêtes existantes
+vector<int> complete_preserve( vector<int> &c) {
+ vector<int> r ;
+ r.push_back(c[0]);
+ for(size_t i = 1 ; i < c.size() ; i++ ) {
+ if (id_arete[make_pair(c[i-1], c[i])])
+ r.push_back(c[i]);
+ else
+ while (r.back() != c[i])
+ r.push_back(use[r.back()][c[i]]);
+ }
+ return r ;
+}
+
+void complete_preserve(vector<int> sol[]) {
+ for (int v = 0; v < n_vehicules; v++)
+ sol[v] = complete_preserve(sol[v]);
+}
+
vector<int> complete ( vector<int> & c)
{
vector<int> r ;
diff --git a/contest/mehdi/a.cpp b/contest/mehdi/a.cpp
@@ -2,6 +2,7 @@
#include <csignal>
#include <bitset>
#include <numeric>
+#include <map>
#include "../louis/louis.cpp"
//#include "../mc/lecture.cpp"
#include "../mc/prune.cpp"
@@ -132,7 +133,7 @@ void mul_pos(int v, uint i, int mul) {
score -= longueur[arete];
}
-pivi cherche_modif(int v, int debut, int fin, int max_add, int score_a_battre) {
+pivi cherche_modif(int v, int debut, int fin, int max_add, int score_a_battre, int temps_a_battre) {
pivi best;
best.first = -1;
for (uint i = 0; i < adj[debut].size(); i++) {
@@ -147,7 +148,7 @@ pivi cherche_modif(int v, int debut, int fin, int max_add, int score_a_battre) {
if (!passages[arete])
score += longueur[arete];
if (!max_add) {
- if (score > score_a_battre) {
+ if (score > score_a_battre || (score == score_a_battre && temps[v] + cout[arete] < temps_a_battre)) {
// fprintf(stderr, "%d > %d (%d -> %d)\n", score, score_a_battre, debut, fin);
best.first = score;
best.second.push_back(fin);
@@ -158,7 +159,7 @@ pivi cherche_modif(int v, int debut, int fin, int max_add, int score_a_battre) {
}
passages[arete]++;
temps[v] += cout[arete];
- pivi cur = cherche_modif(v, voisin, fin, max_add - 1, score_a_battre);
+ pivi cur = cherche_modif(v, voisin, fin, max_add - 1, score_a_battre, temps_a_battre);
if (cur.first > best.first) {
best = cur;
best.second.push_back(voisin);
@@ -187,9 +188,10 @@ bool modif(int v) {
if (pos + rm + 1 > _solution[v].size())
continue;
int prev_score = score;
+ int prev_temps = temps[v];
for (uint dp = 0; dp < rm; dp++)
mul_pos(v, pos + dp, -1);
- pivi mod = cherche_modif(v, _solution[v][pos], _solution[v][pos+rm], MAX_ADD, prev_score);
+ pivi mod = cherche_modif(v, _solution[v][pos], _solution[v][pos+rm], MAX_ADD, prev_score, prev_temps);
if (mod.first < 0) {
for (uint dp = 0; dp < rm; dp++)
mul_pos(v, pos + dp, 1);
@@ -202,8 +204,9 @@ bool modif(int v) {
// debug_car(v);
for (uint j = 0; j < mod.second.size(); j++)
mul_pos(v, pos + j, 1);
- fprintf(stderr, "%d\t+%d\tModif longueur %zu (rm %d) à vehicule %d pos %d\n", score, score - prev_score, mod.second.size(), rm ,v, pos);
- if (score <= prev_score) {
+ int dt = temps[v] - prev_temps;
+ fprintf(stderr, "%d\t+%d\tModif longueur %zu (rm %d) à vehicule %d pos %d (t %c= %d)\n", score, score - prev_score, mod.second.size(), rm, v, pos, dt > 0 ? '+' : '-', dt > 0 ? dt : -dt);
+ if (score < prev_score || (score == prev_score && dt > 0)) {
debug_car(v);
exit(0);
}
@@ -310,6 +313,7 @@ bool prune_and_complete() {
skipped_last = true;
}
}
+ /*
if (skipped_last) {
while (res.back() != _solution[v].back()) {
int n = use[res.back()][_solution[v].back()];
@@ -321,6 +325,7 @@ bool prune_and_complete() {
res.push_back(n);
}
}
+ */
_solution[v] = res;
}
int dt = prev_temps - temps_total();
@@ -462,6 +467,88 @@ void positions_choisies() {
_solution[7].push_back(plus_proche(48.886053,2.288048));
}
+inline double dist(int s1, int s2) {
+ return hypot(longitude[s1] - longitude[s2], latitude[s1] - latitude[s2]);
+}
+
+void gloutonne() {
+ const double INF = 123456789.0;
+ int GLOUTONNE_MAX = n_aretes;
+ vector<pair<int, int> > ar;
+ for (int a = 1; a <= n_aretes; a++)
+ ar.push_back(make_pair(longueur[a], a));
+ sort(ar.begin(), ar.end());
+ GLOUTONNE_MAX = min(GLOUTONNE_MAX, int(ar.size()));
+ for (int i = 0; i < GLOUTONNE_MAX; i++) {
+ int a = ar[i].second;
+ if (passages[a])
+ continue;
+ double d[n_vehicules];
+ bool o[n_vehicules];
+ uint p[n_vehicules];
+ for (int v = 0; v < n_vehicules; v++) {
+ d[v] = INF;
+ if (temps[v] >= t_autorise)
+ continue;
+ for (uint j = 0; j < _solution[v].size(); j++) {
+ double f = dist(_solution[v][j], depart[a]);
+ if (f < d[v]) {
+ d[v] = f;
+ o[v] = false;
+ p[v] = j;
+ }
+ if (dbsens[a]) {
+ double e = dist(_solution[v].back(), arrivee[a]);
+ if (e < d[v]) {
+ d[v] = e;
+ o[v] = true;
+ p[v] = j;
+ }
+ }
+ }
+ }
+ int v = min_element(d, d + n_vehicules) - d;
+ if (d[v] == INF)
+ break;
+ int go;
+ if (o[v])
+ go = arrivee[a];
+ else
+ go = depart[a];
+ fprintf(stderr, "Gloutonne, vehicule %d, pos %u va à %d pour arête %d\n", v, p[v], go, a);
+ vector<int> toinsert;
+ toinsert.push_back(_solution[v][p[v]]);
+ while (toinsert.back() != go) {
+ int u = use[toinsert.back()][go];
+ int b = id_arete[make_pair(toinsert.back(), u)];
+ if (!passages[b])
+ score += longueur[b];
+ passages[b]++;
+ temps[v] += cout[b];
+ toinsert.push_back(u);
+ }
+ if (p[v] < _solution[v].size() - 1) {
+ if (!passages[a]) {
+ toinsert.push_back(go == arrivee[a] ? depart[a] : arrivee[a]);
+ temps[v] += cout[a];
+ score += longueur[a];
+ }
+ passages[a]++;
+ go = _solution[v][p[v]];
+ while (toinsert.back() != go) {
+ int u = use[toinsert.back()][go];
+ int b = id_arete[make_pair(toinsert.back(), u)];
+ if (!passages[b])
+ score += longueur[b];
+ passages[b]++;
+ temps[v] += cout[b];
+ toinsert.push_back(u);
+ }
+ }
+ _solution[v].erase(_solution[v].begin() + p[v]);
+ _solution[v].insert(_solution[v].begin() + p[v], toinsert.begin(), toinsert.end());
+ }
+}
bool try_ameliore_louis() {
int prev_score = score;
@@ -480,6 +567,15 @@ bool try_ameliore_louis() {
return false;
}
+void print_stats() {
+ map<int, int> nb_passages;
+ for (int a = 1; a <= n_aretes; a++)
+ nb_passages[passages[a]]++;
+ int m = nb_passages.rbegin()->first;
+ for (int p = 0; p <= m; p++)
+ fprintf(stderr, "%d route%s à %d passage%s\n", nb_passages[p], nb_passages[p] >= 2 ? "s" : "", p, p >= 2 ? "s" : "");
+}
+
int main(int argc, char *argv[]) {
/*
Usage: a.out [INTERM_BASENAME [INIT_SOLUTION]]
@@ -503,9 +599,15 @@ int main(int argc, char *argv[]) {
positions_choisies();
complete_all(_solution);
#endif
+#ifdef GLOUTONNE
+ gloutonne();
+ tronque_solution(_solution);
+#endif
}
calc_glob();
+ affiche_score();
+ print_stats();
debug_sol();
prune_and_complete();
