Minimum spanning tree

Aiuto
1

Salve a tutti!

Ho risolto il problema mst con l’algoritmo di Kruskal, ma diciamo che ce l’ho fatta davvero per poco. Il tempo limite era di 2sec, io ce ne ho messi 1.990… non è l’algoritmo giusto da utilizzare? Tra l’altro è l’unico che ricordo, Prim non l’ho mai imparato ma mi pare che fosse più lento no? (non ho avuto il tempo di controllare comunque)
2

In realtà dipende dall’implentazione, io con kruskal sto sui 0.34s,
magari hai scritto qualcosa di non troppo giusto che rallenta di molto l’esecuzione.

3

Ho controllato, la mia implementazione è identica a quella del libro “Competitive programming 3”, dopo tutto l’ho imparata da lì.

Comunque mi va quasi fuori tempo solo nel testcase 015, tutti gli altri non superano i 0.480s.
4

Non ho il libro sottomano, la versione del CP3 usa un while per creare l’MST giusto?

5

No, ordina gli archi e poi li prende (utilizzando una Union Find) con un for tutti quelli i cui vertici non appartengono a uno stesso insieme.

6

Il for termina quando prendi N-1 archi?

7

Ah… no. Non pensavo si mangiasse tanto tempo. Ora lo risolve in 1.42, più di mezzo secondo in meno.

Thanks
8

bhè se non ti fermi controlli tutti gli archi ( 1M )
se ti fermi controlli circa 10k, nel caso migliore ti risparmi 990000 chiamate alla funzione unionfind…

9

Il primo codice che ho inviato va in 0.76 senza fermarsi a N-1… Mi sa che hai comunque qualche altro problema

10

Forse la lentezza è nella lettura dell’input. Se usi cin/cout prova a inserire ios_base::sync_with_stdio(false); come prima istruzione della main().

11
Forse la lentezza è nella lettura dell'input. Se usi cin/cout prova a inserire ios_base::sync_with_stdio(false); come prima istruzione della main().

wil93

Non volevo agire sull'I/O, mi sembra come barare. Però evidentemente usare l'freopen() è abbastanza lento rispetto all'utilizzo di ifstream/ofstream (cosa che non sapevo).

Ora lo risolve in 0.70s, grazie :)
12
evidentemente usare l'freopen() è abbastanza lento rispetto all'utilizzo di ifstream/ofstream

Lawliet

Uhm... Non credo sia freopen il problema, sono proprio ifstream/ofstream che sono lenti, a meno che non si disattivi la sincronizzazione come in questo caso (e se lo si fa a volte possono anche essere più veloci di scanf/printf).

UPD: Ah no, in effetti hai ragione, sono cin e cout che fanno la sincronizzazione (un generico ifstream/ofstream non ne ha motivo).