Nu aveti permisiuni pentru a descarca fisierul grader_test6.ok
Cod sursa(job #1094647)
Utilizator | UAIC Alexandru Ionita Juve45 | Data | 29 ianuarie 2014 17:57:01 |
---|---|---|---|
Problema | Arbore partial de cost minim | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.54 kb |
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define x first
#define y second
#define dmax 200000
typedef pair<int, pair<int, int> > muchie;
muchie rt[dmax];
int st, sum, n, m, root[dmax];
vector <int > c[dmax], v;
void read()
{
freopen("apm.in", "r", stdin);
scanf("%i%i",&n,&m);
for(int i=1; i<=m; i++)
{
scanf("%i%i%i", &rt[i].y.x, &rt[i].y.y, &rt[i].x);
}
for(int i=1; i<=n; i++)
root[i]=i;
}
void conex(int a, int b)
{
v.pb(b);
v.pb(a);
{
if(c[a].size()>c[b].size())
{
int ca=a;
a=b;
b=ca;
}
//subordonez pe a la b;
c[b].pb(a);
for(int i=0; i<c[a].size(); i++)
{
root[c[a][i]] = b;
c[b].pb(c[a][i]);
}
c[a].clear();
root[a]=b;
}
}
bool connected(int a, int b)
{
if(root[a]==root[b])
return true;
return false;
}
void apm()
{
st=1;
for(int i=1; i<n; i++)
{
while(connected(rt[st].y.x, rt[st].y.y))
st++;
conex(rt[st].y.x,rt[st].y.y);
sum=sum+rt[st].x;
st++;
}
}
void write()
{
freopen("apm.out", "w", stdout);
printf("%i%c%i%c", sum, '\n',n-1, '\n');
for(int i=0; i<2*n-2; i+=2)
printf("%i%c%i%c", v[i],' ', v[i+1],'\n');
}
int main()
{
read();
sort(rt+1, rt+m-1);
apm();
write();
return 0;
}