Ho visto ora il nuovo forum e ne approfitto per chiedere come si risolveva il problema footing delle territoriali? In gara ho tentato di fare i casi di collegamenti di lunghezza unitaria, ma ne è uscito una DFS che funzionava quando voleva dato che il ragionamento che ho fatto probabilmente era sbagliato. Detto ciò non ho la minima idea di come si possa risolvere per fare 100 punti.
Se non sbaglio, una la soluzione (non ottima) è simile a quella del problema “barbablu”, con piccole ottimizzazioni.
ah cacchio avevo provato a fare lunedì barbablu, una volta scritto non mi funzionava e non ho provato a cercare gli errori abbandonandolo… forse avrei dovuto provare a farlo fino in fondo. comunque grazie, appena lo mettono sul correttore ci lavoro
Non proprio uguale insomma… Penso che un’idea analoga, ben ottimizzata, vada bene
Penso che facendo partire una funzione da ogni nodo, che brutalmente provi tutti i percorsi, stando attenti a certi vincoli quali che la lunghezza minima non sia stata superata, e che i nodi “già provati” non siano presenti, si possa giungere ad una soluzione… Sì, è esponenziale, e non escludo ce ne siano di migliori
Ah beh si così è esponenziale. Io ho una soluzione O(n^2logn) ma non so se è la migliore (anche se credo di sì).
Probabilmente (anzi sicuramente) tirando in ballo una versione modificata di Dijkstra si può fare di meglio
Per ora non abbiamo di meglio (anche se probabilmente intendevi dire O(nm\log n) )
Posto qui per non creare un altro topic.
Per risolvere queste esercizio avevo pensato ad un algoritmo del genere:
Applico l’algoritmo di Dijkstra per visitarmi tutti i nodi e le relative distanze minime, ma se trovo un nodo già visitato allora ci sarà come minimo un ciclo (al limite partendo dal primo nodo). Allora mi cerco il predecessore comune § tra il nodo che sto visitando in questo momento (u) e il nodo, a lui collegato, che invece avevo già visitato (v). A questo punto la lunghezza del ciclo minimo che coinvolge questi due nodi sarà: lunghezza_ciclo = (distanza[u]-distanza[p]) + (distanza[v]-distanza[p]) + peso_arco_UV.
Mi sembra un algoritmo corretto, ma non ne sono sicuro (ed infatti becca 50/100 punti). In quali casi fallisce? Io non sono riuscito ad individuarli.
Inoltre la complessità dovrebbe essere O(n^2logn).
Grazie per l’aiuto, questo è il codice:
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <climits>
#include <algorithm>
#define MAXN 1005
using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vi;
vi G[MAXN];
int N, M, dist[MAXN], prec[MAXN], minimo=INT_MAX;
bool precU[MAXN], vis[MAXN];
int main(){
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin >> N >> M;
for(int i=0, u, v, w; i<M; i++){
cin >> u >> v >> w;
G[u].push_back( make_pair(w, v) );
G[v].push_back( make_pair(w, u) );
}
priority_queue< ii, vi, greater<ii> > Q;
fill_n(dist, N+1, INT_MAX);
fill_n(prec, N+1, N);
dist[1] = 0;
Q.push( make_pair(0, 1) );
prec[1] = 0;
while(!Q.empty()){
int u = Q.top().second; Q.pop();
if(vis[u]) continue;
for(int i=0; i<G[u].size(); i++){
int v = G[u][i].second, w = G[u][i].first;
if( vis[v] && v!=1){
fill_n(precU, N+1, false);
int p = prec[u], d;
while(p>0){
precU[p]=true;
p = prec[p];
}
p = prec[v];
while(p>0){
if(precU[p]) break;
p = prec[p];
}
d = dist[u]+dist[v]+w-dist[p]-dist[p];
minimo = min(d, minimo);
}
if( w+dist[u] < dist[v]){
dist[v] = w+dist[u];
prec[v] = u;
Q.push( make_pair(dist[v], v) );
}
}
vis[u] = true;
}
cout << minimo << "\n";
return 0;
}
Nel caso di esempio mi pare che produca 6 invece di 8
Mmmh purtroppo l’ho fatto ieri a mezzanotte su Windows con notepad ahahah non me n’ero accorto che falliva sul primo perché facendo il ragionamento su carta usciva 8… questo pomeriggio vedo di installarmi il compilatore.
Ma il ragionamento fila secondo te?
Io l’ho risolto usando una versione modificata di Dijkstra che ha complessità O(N^2logN+NM) , che a quanto sembrerebbe è ottimale, ma mi gira in 0.987 s.
Uhm… ho appena mandato la nostra soluzione.cpp (“ufficiale”, che si può trovare su github) che ha quella complessità, ma gira in 0.111s
Appena scesa a 0.055s fermando Dijkstra quando il cammino è oltre il minimo trovato fin ora.
A parte il caso d’esempio, nel codice tieni in considerazione la possibilità che il grafo non sia connesso?
Uhm… No. Ho dato per scontato che non ci fossero.
Comunque ora il caso d’esempio lo prende, ho modificato un controllo all’interno del ciclo in modo da non andare al proprio predecessore (so che dovrebbe essere ovvio, ma pensavo di averlo controllato ma me n’ero dimenticato). Ora prende 80/100… Provo a vedere se il problema dell’ancora mancato 100/100 sia quello di un grafo non connesso.
A pensarci bene non dovrebbero essere presenti grafi non connessi nei casi di test (nonostante siano permessi), perché nei casi generati si ha sempre M \ge N.
EDIT: no, non è vero, possono benissimo esserci grafi non connessi (banalmente: potrebbe essere un grafo con M \ge N ma con il nodo 1 isolato da tutti).
Ho fatto un algoritmo che dovrebbe funzionare anche con i grafi non connessi, ma sempre 80/100.
Il codice è questo http://pastebin.com/GicYYFZU
Comincio a pensare che l’algoritmo è sbagliato
EDIT: Non è che si potrebbero avere i testcase su cui fallisce (che sarebbero 005 e 009)?
Ho provato a generarne uno piccolo (che fallisce ugualmente)
4 4
1 3 3
4 1 3
2 4 1
2 1 1
Un’altra svista che ho sistemato ponendo dist[0]=0; in quanto se il ciclo terminava in 1, il quale avevo come predecessore 0, questo dava chiaramente problemi.
Ora quel testcase dà come risultato 5, così come dovrebbe essere, ma ancora non mi smuovo dagli 80/100.
Codice: http://pastebin.com/rHTjTied