Territoriali Footing

Aiuto
5

Non proprio uguale insomma… Penso che un’idea analoga, ben ottimizzata, vada bene

6

@CarlaZZ puoi spiegarmi meglio la tua idea? Perché se ricordo bene Barbablù non credo funzioni

7

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

8

Ah beh si così è esponenziale. Io ho una soluzione O(n^2logn) ma non so se è la migliore (anche se credo di sì).

1 Mi Piace
9

Probabilmente (anzi sicuramente) tirando in ballo una versione modificata di Dijkstra si può fare di meglio

10

Per ora non abbiamo di meglio (anche se probabilmente intendevi dire O(nm\log n) :stuck_out_tongue:)

3 Mi Piace
11

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;
}
12

Nel caso di esempio mi pare che produca 6 invece di 8 :confused:

13

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?

14

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. :sweat_smile:

15

Uhm… ho appena mandato la nostra soluzione.cpp (“ufficiale”, che si può trovare su github) che ha quella complessità, ma gira in 0.111s :smile:

Appena scesa a 0.055s fermando Dijkstra quando il cammino è oltre il minimo trovato fin ora.

16

A parte il caso d’esempio, nel codice tieni in considerazione la possibilità che il grafo non sia connesso?

17

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.

18

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).

19

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 :sweat_smile:

EDIT: Non è che si potrebbero avere i testcase su cui fallisce (che sarebbero 005 e 009)?

20

Ho provato a generarne uno piccolo (che fallisce ugualmente)

4 4
1 3 3
4 1 3
2 4 1
2 1 1
21

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

22

Eccone un altro :stuck_out_tongue:

4 4
3 4 1
4 2 1
2 3 3
3 1 3
23

Adesso anche quello va bene… Sempre un altro errore banale. Se il predecessore comune fosse stato “v” stesso, l’algoritmo di prima non avrebbe funzionato.
Modificando opportunamente l’input creato da te me lo fa bene, ma ancora sono a 80 punti :frowning:
Sto perdendo le speranze ahahah http://pastebin.com/tN9v2eSh

24

:grin:

4 5
3 1 3
2 1 3
4 2 2
3 4 1
2 3 3