Stavo provando a fare un algoritmo per il minimum spanning tree. Ho cercato di seguire il ragionamento del kruskal’s algorithm (lo ho trovato solo implementato con classi e strutture di cui capisco poco), quel che ho fatto è stato inserire i due nodi con la distanza in una priority queue, in modo da ottenere le distanze ordinate, poi finchè la queue non è vuota controlla se i due nodi sono visitati, o raggiungibili, vi allego il programma perchè penso sia più facile comprendere così che a parole:
#include <bits/stdc++.h>
#define MAXN 10001
using namespace std;
vector<int> adj[MAXN];
priority_queue<pair<int ,pair<int, int> > > pq;
priority_queue<pair<int,int> > pr;
int vis[MAXN];
int c=0;
int vis2[MAXN];
long long Matrix[MAXN][2];
long long N;
void DFS(int s,int end){ //se trova il collegamento che porta il nodo s al nodo end, finisce
//restituendo 1 a sol, che lo restituisce dove viene chiamato
if(s==end){
c=1;
}
if(vis2[s]==1 || c==1) return;
vis2[s]=1;
for(int u=0;u<adj[s].size();u++){
DFS(adj[s][u], end);
}
}
int sol(int s, int end){
c=0;
for(int u=0;u<N;u++) vis2[u]=0;
DFS(s,end);
return c;
}
int main(void)
{
FILE *fr, *fw;
fr = fopen("input.txt", "r");
fw = fopen("output.txt", "w");
long long M,i;
long long a,b,c,r=0;
assert(2 == fscanf(fr, "%lld%lld", &N, &M));
for(i=0;i<M;i++){
assert(3 == fscanf(fr, "%lld%lld%lld", &a, &b, &c));
pq.push(make_pair(-c,make_pair(a,b))); //ordina la queue per distanza
}
while(!pq.empty()){
if((vis[pq.top().second.first]==0 || vis[pq.top().second.second]==0) || (!sol(pq.top().second.first,pq.top().second.second))){ //controlla se entrambi i nodi che hanno tra loro distanza
// minore siano visitati. la funzione invece chiama una DFS perchè
// nel caso siano entrambi già stati visitati bisogna vedere se sono collegati
vis[pq.top().second.first]=1; //i due nodi sono visitati
vis[pq.top().second.second]=1;
adj[pq.top().second.first].push_back(pq.top().second.second); //crea il tree aggiungendo gli archi
adj[pq.top().second.second].push_back(pq.top().second.first);
r+=-pq.top().first; //aumenta il risultato della distanza di tale arc
if(pq.top().second.first<pq.top().second.second)pr.push(make_pair(-pq.top().second.first,-pq.top().second.second)); //normalmente non servirebbe ma il problema
//sul sito richiede anche i nodi che formano l'albero perciò li salva in un altra queue
// (so che non servirebbe ma dai casi di esempio vedevo che li voleva ordinati e non so se sarebbe errore o meno non metterli così)
else pr.push(make_pair(-pq.top().second.second,-pq.top().second.first));
}
pq.pop(); //rimuove dalla queue nodi e arco controllati
}
fprintf(fw, "%d\n", r);
while(!pr.empty()){
fprintf(fw, "%d %d\n", -pr.top().first, -pr.top().second);
pr.pop();
}
return 0;
}
Dall’esercizio mi da qualche risultato sbagliato, se trovate qualche caso in cui non funziona il programma fatemi sapere. (in alcuni casi va anche out di tempo ma onestamente non saprei come velocizzare, al massimo potrei fare un altra if che fa controllare tutto il grafo solo quando entrambi i nodi sono già stati visitati)
