Sto provando questo problema, e la mia idea è quella di eseguire prima di tutto una bfs per avere la distanza minima in nodi tra i due computer (William e Luca), e poi dijkstra per avere la portata minima.
Ovviamente in dijkstra invece di avere la somma dei pesi degli archi come lunghezza di un percorso uso il minimo dei pesi.
Per ora ho implementato solo la prima parte, la visita in ampiezza, che in locale funziona senza problemi. Per prova l’ho caricata sul correttore (sottoposizione 48228), dove ovviamente ho avuto 0/100. La cosa strana, però, è che alcuni testcase me li dà come falliti con questo errore: “Execution killed with signal 11 (could be triggered by violating memory limits)”. Questo è il codice che uso, è possibile che esaurisca veramente la memoria?
#include <vector>
#include <utility>
#include <list>
#include <bitset>
using namespace std;
vector<vector<pair<int, int> > > *arcs;
// bfs
int calculateMinLength(int startNode, int finalNode)
{
// node length
list<pair<int, int> > queue;
bitset<MAXN> visited;
queue.push_back(make_pair(startNode, 0));
visited[startNode] = true;
vector<pair<int, int> >::iterator it;
while(!queue.empty())
{
// get next node
pair<int, int> node = queue.front();
queue.pop_front();
// check if we reached our goal
if(node.first == finalNode)
return node.second;
// otherwise continue the visit
vector<pair<int, int> > arcList = (*arcs)[node.first];
for(it = arcList.begin(); it != arcList.end(); ++it)
{
if(!visited[(*it).first])
{
visited[(*it).first] = true;
queue.push_back(make_pair((*it).first, node.second + 1));
}
}
}
return -1;
}
// modified Dijkstra
int calculateMinCapacity(int start, int end, int maxLen)
{
return 12;
}
int Analizza(int N, int M, int W, int L, int arc_from[], int arc_to[], int cap[], int, int)
{
// save all arcs in a better format
arcs = new vector<vector<pair<int, int> > >(M);
for(int i = 0; i < M; i++)
{
(*arcs)[arc_from[i]].push_back(make_pair(arc_to[i], cap[i]));
(*arcs)[arc_to[i]].push_back(make_pair(arc_from[i], cap[i]));
}
// calculate maximum possible length with a bfs
int maxLen = calculateMinLength(W, L);
// now execute the modified dijkstra search with the maximum length
int capacity = calculateMinCapacity(W, L, maxLen);
printf("%d\n", capacity);
return 0;
}
Dario