Pagini recente » Diferente pentru problema/infasuratoare intre reviziile 8 si 80 | Cod sursa (job #2174807)
#include <fstream>
#include <vector>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector <pair<int, pair <int,int > > > edges ;
int sola[400005],solb[400005];
int n,m;
int grad[200005];
int fathers[400005];
int find(int x)
{
if(fathers[x]==x)return x;
return find(fathers[x]);
}
void uniune (int x,int y)
{
int fx=find(x);
int fy=find(y);
if(fx>fy)
swap(fx,fy);
fathers[fx]=fy;
}
int main()
{
int a,b,w;
f>>n>>m;
for(int i=1;i<=m;i++)
{
f>>a>>b>>w;
edges.push_back(make_pair(w,make_pair(a,b)));
}
for(int i=1;i<=n;i++)
fathers[i]=i;
sort(edges.begin(),edges.end());
int mst_weight=0,mst_edges=0,mst_ni=0;
while(mst_edges<n-1)
{
a=edges[mst_ni].second.first;
b=edges[mst_ni].second.second;
w=edges[mst_ni].first;
if(find(a)!=find(b))
{
mst_edges++;
mst_weight+=w;
uniune(a,b);
sola[mst_edges]=a;
solb[mst_edges]=b;
}
mst_ni++;
}
g<<mst_weight<<'\n';
g<<mst_edges<<'\n';
for(int i=1;i<=mst_edges;i++)
g<<sola[i]<<' '<<solb[i]<<'\n';
return 0;
}