Aiuto Bottleneck 39/100 con BFS

Aiuto
1

Stavo provando a fare Bottleneck, ma mi dà soluzione errata in alcuni subtask (nel 4, nel 6 e nel 7 ne fallisce alcuni. Il subtask 5 invece funziona benissimo). Per il subtask 4 avevo pensato di individuare la posizione in righe/colonne di William e Luca, creare un “rettangolo” e individuare all’ interno di questo l’arco con peso minore, poichè è molto più veloce della soluzione che ho implementato per gli altri subtask. Per gli altri uso una BFS che cerca tutti i percorsi più corti tra W e L salvandosi il peso dell’arco più leggero di ogni percorso. Se poi il percorso arriva ad L nel numero minimo di passi(che scopro appena arrivo per la prima volta ad L), aggiorno la variabile minimo con minimo=min(minimo, arco_più_piccolo_del_percorso).

#include<bits/stdc++.h>
using namespace std;

const int oo = numeric_limits<int>::max();

int Analizza(int N, int M, int W, int L, int arco_da[], int arco_a[], int capacita[], int R, int C) {
  vector<vector<pair<int, int>>> graph(N);
  int minimo = oo;
  W--; L--;
  for(int i=0; i<M; i++){
    graph[arco_da[i]-1].push_back({arco_a[i]-1, capacita[i]});;
    graph[arco_a[i]-1].push_back({arco_da[i]-1, capacita[i]});;
  }

  if(R != -1){
    // se sono nel subtask 4 utilizzo il metodo a "rettangolo"
    pair<int, int> posW = {W%C, W/C};
    pair<int, int> posL = {L%C, L/C};

    int min_arch = oo;

    pair<int, int> start = {min(posW.first, posL.first), min(posW.second, posL.second)};
    pair<int, int> end = {max(posW.first, posL.first), max(posW.second, posL.second)};

    // cerr << "Start: " << start.first + 1<< " " << start.second + 1 << endl;
    // cerr << "End: " << end.first + 1 << " " << end.second + 1 << endl;
    for(int i=start.first; i<=end.first; i++){
      for(int j=start.second; j<=end.second; j++){
        // cerr << "Iter: " << i + 1 << " " << j + 1 << " " << C*j + i << endl;
        for(auto n: graph[C*j + i]){
          if(n.first > (C*j + i) and n.first <= max(L, W) ){
            // cerr << n.first << endl;
            min_arch = min(min_arch, n.second);
          }
        }
      }
    }
    return min_arch;
  }else{
    // BFS
    vector<bool> esplorati(N);
    queue<pair<int, int>> frontiera;
    frontiera.push({W, oo});

    pair<int, int> curr;
    int size, i;
    bool to_break = false;
    while(true){
      size = frontiera.size();
      for(i=0; i<size; i++){
        curr = frontiera.front();
        frontiera.pop();

        for(auto n: graph[curr.first]){
          if(not esplorati[n.first]){
            if(n.first == L){
              to_break = true;
              minimo = min({minimo, min(curr.second, n.second)});
            }else{
              frontiera.push({n.first, min(curr.second, n.second)});
              esplorati[n.first] = true;
            }
          }
        }
      }
      if(to_break) break;
    }
  }
  return minimo;
}

Qualche idea?
Grazie Mille

2

Update

Ho trovato un errore nel metodo BFS.
In un caso come questo:

image
image1491×709 21.5 KB

Dopo che BFS arriva ai nodi con distanza 2, processa prima quello in alto, si salva che l’ha già visitato e ignora il possibile percorso passante per il nodo in basso. Ho aggiornato il codice e ora fa 61/100:

#include<bits/stdc++.h>
using namespace std;

const int oo = numeric_limits<int>::max();

template <typename T> int sgn(T val) {
    return (T(0) <= val) - (val < T(0));
}

int Analizza(int N, int M, int W, int L, int arco_da[], int arco_a[], int capacita[], int R, int C) {
  vector<vector<pair<int, int>>> graph(N);
  int minimo = oo;
  W--; L--;
  for(int i=0; i<M; i++){
    graph[arco_da[i]-1].push_back({arco_a[i]-1, capacita[i]});;
    graph[arco_a[i]-1].push_back({arco_da[i]-1, capacita[i]});;
  }

  if(R != -1){
    pair<int, int> posW = {W%C, W/C};
    pair<int, int> posL = {L%C, L/C};

    int min_arch = oo;

    pair<int, int> start = {min(posW.first, posL.first), min(posW.second, posL.second)};
    pair<int, int> end = {max(posW.first, posL.first), max(posW.second, posL.second)};

    // cerr << "Start: " << start.first + 1<< " " << start.second + 1 << endl;
    // cerr << "End: " << end.first + 1 << " " << end.second + 1 << endl;
    for(int i=start.first; i<=end.first; i++){
      for(int j=start.second; j<=end.second; j++){
        // cerr << "Iter: " << i + 1 << " " << j + 1 << " " << C*j + i << endl;
        for(auto n: graph[C*j + i]){
          if(n.first > (C*j + i) and n.first <= max(L, W) ){
            // cerr << n.first << endl;
            min_arch = min(min_arch, n.second);
          }
        }
      }
    }
    return min_arch;
  }else{
    vector<bool> esplorati(N);
    vector<int> new_esplorati = {};
    queue<pair<int, int>> frontiera;
    frontiera.push({W, oo});

    pair<int, int> curr;
    int size, i;
    bool to_break = false;
    while(true){
      size = frontiera.size();
      for(i=0; i<size; i++){
        curr = frontiera.front();
        frontiera.pop();

        for(auto n: graph[curr.first]){
          if(not esplorati[n.first]){
            if(n.first == L){
              to_break = true;
              minimo = min({minimo, min(curr.second, n.second)});
            }else{
              frontiera.push({n.first, min(curr.second, n.second)});
              new_esplorati.push_back(n.first);
            }
          }
        }
      }
      for(auto n: new_esplorati){
        esplorati[n] = true;
      }
      new_esplorati.clear();
      if(to_break) break;
    }
  }
  return minimo;
}

Nel subtask 4 utilizza ancora il vecchio metodo, per cui non è cambiato(Ho provato a sostituire R != -1 ma và fuori ram). Invece il 6 ora funziona, mentre il 7 ora ha problemi di ram.

Edit:

Ho scoperto che esiste l’algoritmo di ricerca bidirezionale che dovrebbe svolgere la stessa funzione del BFS usando circa 1/2 della ram(credo). Ho provato ad implementarlo ma per ora non ho ottenuto grossi successi.

3

Ciao, purtroppo i problemi che nascono dall’utilizzo di troppa RAM spesso richiedono un’implementazione alternativa per essere risolti – l’ottimizzazione spesso non basta.
Riguardo alla tua implementazione, esiste un algoritmo che possa risolvere tutti i subtask (quindi ignorando le variabili R e C): con una variante della BFS si può prendere 100/100 su questo problema in una cinquantina di righe di codice!

Suggerimenti
  • Partendo dal computer W, qual è la lunghezza minima da percorrere?
  • Mentre visiti i nodi per rispondere alla domanda precedente, conviene memorizzare la capacità complessiva da W al nodo che l’algoritmo sta valutando?
  • Esiste un modo per escludere alcuni nodi da visitare?

Spero di essere stato chiaro, se ti dovesse servire qualche chiarimento scrivi pure!

1 Mi Piace
4

image

Grazieee!!!
Ho aggiunto un controllo per evitare di aggiungere nuovi nodi alla queue una volta trovato il nodo di destinazione e ho modificato il sistema di inserimento di nuovi nodi nella queue per evitare di inserire più volte uno stesso nodo, ora funziona perfettamente. La capacità complessiva minima di ogni nodo viene invece memorizzata usando una queue<pair<numero_nodo, peso_minimo_percorso>>

#include<bits/stdc++.h>
using namespace std;

const int oo = numeric_limits<int>::max();

int Analizza(int N, int M, int W, int L, int arco_da[], int arco_a[], int capacita[], int R, int C) {
  vector<vector<pair<int, int>>> graph(N);
  int minimo = oo;
  W--; L--;
  for(int i=0; i<M; i++){
    graph[arco_da[i]-1].push_back({arco_a[i]-1, capacita[i]});;
    graph[arco_a[i]-1].push_back({arco_da[i]-1, capacita[i]});;
  }

  vector<bool> esplorati(N);
  unordered_map<int, int> new_esplorati = {};
  queue<pair<int, int>> frontiera;
  frontiera.push({W, oo});

  pair<int, int> curr;
  int size, i;
  bool to_break = false;
  while(true){
    size = frontiera.size();
    for(i=0; i<size; i++){
      curr = frontiera.front();
      frontiera.pop();

      for(auto n: graph[curr.first]){
        if(not esplorati[n.first]){
          if(n.first == L){
            to_break = true;
            minimo = min({minimo, min(curr.second, n.second)});
          }else{
            if(not to_break){
              if(new_esplorati.count(n.first) > 0){
                new_esplorati[n.first] = min(min(curr.second, n.second), new_esplorati[n.first]);
              }else{
                new_esplorati[n.first] = min(curr.second, n.second);
              }
            }
          }
        }
      }
    }
    if(to_break) break;
    for(auto n: new_esplorati){
      esplorati[n.first] = true;
      frontiera.push(n);
    }
    new_esplorati.clear();
  }
  return minimo;
}
5

Complimenti! Ovviamente si può continuare ad ottimizzare, però immagino che la soluzione immaginata dagli autori sia proprio questa.
Buona fortuna (e spero di essere stato d’aiuto), se ti dovesse servire altro non esitare a chiedere nel forum :slight_smile:

1 Mi Piace