bidirezionale spanning tree

Question

mi sono imbattuto in questa domanda da interviewstreet.com

macchine hanno ancora una volta attaccato il regno di Xions. Il regno di Xions ha N città e N-1 strade bidirezionali. La rete stradale è tale che vi sia un percorso unico tra qualsiasi coppia di città.

Morpheus ha la notizia che K Machines sta pianificando di distruggere l'intero regno . Queste macchine vivono inizialmente in K diverse città del regno e in qualsiasi momento da ora possono pianificare e lanciare un attacco . Quindi ha chiesto a Neo di distruggere alcune delle strade per interrompere la connessione tra Macchine dopo aver distrutto quelle strade lì. non dovrebbe essere un percorso tra due macchine.

Poiché l'attacco può essere in qualsiasi momento da ora, Neo deve eseguire questa attività il più velocemente possibile. Ogni strada nel regno impiega un certo tempo per distruggere e può essere distrutto solo uno alla volta.

È necessario scrivere un programma che indichi a Neo la quantità minima di tempo necessaria per interrompere la connessione tra le macchine.

Ingresso campione La prima riga dell'ingresso contiene due interi separati da spazi, N e K. Le città sono numerate da 0 a N-1. Quindi seguire le linee N-1 , ciascuna contenente tre numeri interi separati da spazio x y z, che significa che c'è una strada bidirezionale che collega la città xe la città y, e per distruggere questa strada e richiede z unità di tempo. Quindi seguire le linee K contenenti ciascuna un numero intero. Ith integer è l'id della città in cui si trova attualmente la macchina .

Formato di uscita Stampa in una singola riga il tempo minimo richiesto a interrompe la connessione tra le macchine.

Esempio Ingresso

5 3 
2 1 8 
1 0 5 
2 4 5 
1 3 4 
2 
4 
0 

Esempio di output

10 

Spiegazione Neo può distruggere la strada che collega città 2 e la città 4 su peso 5, e la strada che collega città 0 e città 1 di peso 5. Come è possibile distruggere una sola strada alla volta, il tempo totale minimo richiesto è 10 unità di tempo. Dopo aver distrutto queste strade, nessuna delle macchine può raggiungere l'altra macchina tramite qualsiasi percorso.

Vincoli

2 <= N <= 100,000 
2 <= K <= N 
1 <= time to destroy a road <= 1000,000 

Qualcuno può dare idea di come affrontare la soluzione.

Answer 1

Tutte e tre le risposte porteranno alla soluzione corretta ma non è possibile raggiungere la soluzione entro il limite di tempo fornito da interviewstreetstreet.com. Devi pensare ad un approccio semplice per risolvere questo problema con successo.

SUGGERIMENTO: iniziare dal nodo in cui è presente la macchina.

Answer 2

Il regno ha N città, N-1 archi ed è completamente collegato, quindi il nostro regno è tree (in teoria grafico). In questa immagine puoi vedere la rappresentazione ad albero del tuo grafico di input in cui le macchine sono rappresentate da vertici rossi.

A proposito, è necessario considerare tutti i percorsi dal vertice di radice a tutti i nodi foglia. Quindi in ogni percorso avresti diversi nodi rossi e durante la rimozione dei bordi dovresti prendere in considerazione solo i nodi rossi vicini. Ad esempio nel percorso 0-10 ci sono due coppie significative - (0,3) e (3,10). E devi rimuovere esattamente un nodo (non meno, non di più) da ciascun percorso che collega i vertici in coppia.

Spero che questo consiglio sia stato utile.

Answer 3

Come detto da altri, un grafico collegato con N vertici e bordi N-1 è un albero.

Questo tipo di problema richiede una soluzione avida; Proverei una modifica di Kruskal's algorithm:

Iniziare con un set di componenti N - 1 per ogni nodo (città). Tieni traccia di quali componenti contengono una città occupata dalla macchina.

Prendere 1 bordo (strada) alla volta, ordinare in base al peso decrescente (iniziando dalle strade più costose da distruggere). Per questo bordo (che collega necessariamente due componenti - il grafo è un albero):

• se entrambi i componenti neigboring contengono una città occupata macchina, questa strada deve essere distrutto, contrassegnare come tale
• altrimenti, merge i componenti neighbouring in uno. Se uno di essi conteneva una città occupata dalla macchina, lo stesso vale per il componente unito.

Quando hai finito con tutti i bordi, restituire la somma dei costi per le strade distrutte.

La complessità è la stessa dell'algoritmo di Kruskal, ovvero quasi lineare per una struttura dati e un metodo di ordinamento ben scelti.

Answer 4

Pjotr ​​ha una risposta corretta (anche se non proprio asintoticamente ottimale), ma questa affermazione

Questo tipo di problema richiede una soluzione avido

richiede davvero la prova, come nel mondo reale (distinto dalla programmazione competitiva), ci sono diversi problemi di questo tipo “ ” per cui la soluzione golosa non è ottimale (ad esempio, questo stesso problema nei grafici generali, che è chiamato taglio multiterminale e d è NP-difficile). In questo caso, la prova consiste nel verificare gli assiomi matroid. Lascia una serie di bordi A & subseteq; E essere indipendente se il grafico (V, E & setminus; A) ha esattamente | A | + 1 componenti collegati contenenti almeno una macchina.

Indipendenza del set vuoto. Trivial.

Proprietà ereditaria. Sia A un set indipendente. Ogni spigolo e ∈ Un unisce due componenti collegate del grafico (V, E & setminus; A) e ogni componente connesso contiene almeno una macchina. Nel riportare indietro nel grafico, il numero di componenti connessi contenenti almeno una macchina diminuisce di 1, quindi A & setminus; {e} è anche indipendente.

Proprietà di incremento. Sia A che B set indipendenti con | A | < | B |. Poiché (V, E & setminus; B) ha più componenti collegati di (V, E & setminus; A), esiste con il principio del piccionaia una coppia di macchine u, v tale che u e v sono disconnessi da B ma non da A. Poiché esiste esattamente un percorso da u a v, B contiene almeno un bordo e su questo percorso e A non può contenere e. La rimozione di A ∪ {e} induce un altro componente connesso contenente almeno una macchina di A, quindi A ∪ {e} è indipendente, come richiesto.

Answer 5

Scrivo un codice e ho incollato tutti i test.

#include <iostream> 
#include<algorithm> 
using namespace std; 

class Line { 
public: 
    Line(){ 
     begin=0;end=0; weight=0; 
} 
int begin;int end;int weight; 

bool operator<(const Line& _l)const { 
    return weight>_l.weight; 
} 
}; 

class Point{ 
public: 
Point(){ 
    pre=0;machine=false; 
} 
int pre; 
bool machine; 
}; 

void DP_Matrix(); 
void outputLines(Line* lines,Point* points,int N); 

int main() { 
    DP_Matrix(); 
    system("pause"); 
    return 0; 
} 

int FMSFind(Point* trees,int x){ 
    int r=x; 
    while(trees[r].pre!=r) 
     r=trees[r].pre; 
    int i=x;int j; 
    while(i!=r) { 
      j=trees[i].pre; 
     trees[i].pre=r; 
     i=j; 
    } 
return r; 
} 

void DP_Matrix(){ 
int N,K,machine_index;scanf("%d%d",&N,&K); 
Line* lines=new Line[100000]; 
Point* points=new Point[100000]; 
N--; 
for(int i=0;i<N;i++) { 
    scanf("%d%d%d",&lines[i].begin,&lines[i].end,&lines[i].weight); 
    points[i].pre=i; 
} 
points[N].pre=N; 
for(int i=0;i<K;i++) { 
    scanf("%d",&machine_index); 
    points[machine_index].machine=true; 
} 
long long finalRes=0; 
for(int i=0;i<N;i++) { 
    int bP=FMSFind(points,lines[i].begin); 
    int eP=FMSFind(points,lines[i].end); 
    if(points[bP].machine&&points[eP].machine){ 
     finalRes+=lines[i].weight; 
    } 
    else{ 
     points[bP].pre=eP; 
     points[eP].machine=points[bP].machine||points[eP].machine; 
     points[bP].machine=points[eP].machine; 
    } 
} 
cout<<finalRes<<endl; 
delete[] lines; 
delete[] points; 
} 

void outputLines(Line* lines,Point* points,int N){ 
printf("\nLines:\n"); 
for(int i=0;i<N;i++){ 
    printf("%d\t%d\t%d\n",lines[i].begin,lines[i].end,lines[i].weight); 
} 
printf("\nPoints:\n"); 
for(int i=0;i<=N;i++){ 
    printf("%d\t%d\t%d\n",i,points[i].machine,points[i].pre); 
} 
} 

Answer 6

Iniziare a eseguire un DFS da uno dei nodi della macchina. Inoltre, tieni traccia del bordo con il minimo peso incontrato finora. Non appena trovi il nodo successivo che contiene anche una macchina, elimina il bordo minimo registrato fino a quel momento. Avvia DFS da questo nuovo nodo ora. Ripeti fino a quando non hai trovato tutti i nodi in cui la macchina esiste.

Dovrebbe essere della O (N) in questo modo !!