Pagini recente » Cod sursa (job #2281383) | Cod sursa (job #1353119) | Cod sursa (job #2051118) | Cod sursa (job #842264) | Cod sursa (job #871225)
Cod sursa(job #871225)
#include <fstream>
#define INF 100000001
#define NMAX 2001
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
void citire();
void initializare();
void alg_prim();
void afisare();
struct muchie
{
int y;
double c;
} G[NMAX][NMAX];
int Nr[NMAX], M[NMAX];
int tata[NMAX], cmin[NMAX];
int n, m, start;
int cost; //costul minim al arborelui partial
int main()
{
citire();
initializare();
alg_prim();
afisare();
return 0;
}
void citire()
{
int i;
int x, y, c;
fin>>n>>m;
start=1;
for(i=1;i<=m;i++)
{
fin>>x>>y>>c;
Nr[x]++; // il pun pe y in lista de adiacenta a lui x
G[x][Nr[x]].y=y;
G[x][Nr[x]].c=c;
Nr[y]++; //il pun pe x in lista de adiacenta a lui y
G[y][Nr[y]].y=x;
G[y][Nr[y]].c=c;
}
}
void initializare()
{
int i;
for(i=1;i<=n;i++)
{
cmin[i]=INF;
tata[i]=start;
}
for(i=1;i<=Nr[start];i++) //daca am muchie de la start la i atunci pun costul muchiei
cmin[G[start][i].y]=G[start][i].c;
tata[start]=0;
cmin[start]=0;
M[start]=1;
}
void alg_prim()
{
int i, j;
int mn, vf;
for(i=1;i<=n-1;i++)
{
mn=INF+1;
for(j=1;j<=n;j++) //calculez minimul din cmin
if(M[j]==0 && cmin[j]<mn)
{
mn=cmin[j];
vf=j; //retin si vf unde am gasit minimul
}
M[vf]=1; //il selectez
//fout<<vf<<' '<<tata[vf]<<'\n';
cost+=mn;
//actualizez costurile
for(j=1;j<=Nr[vf];j++)
if(M[G[vf][j].y]==0 && cmin[G[vf][j].y]>G[vf][j].c)
{
cmin[G[vf][j].y]=G[vf][j].c;
tata[G[vf][j].y]=vf;
}
}
}
void afisare()
{
int i;
fout<<cost<<'\n'; //costul minim al arborelui partial
fout<<n-1<<'\n';
for(i=2;i<=n;i++)
fout<<i<<' '<<tata[i]<<'\n';
}