Pagini recente » Cod sursa (job #228131) | Cod sursa (job #253073) | Cod sursa (job #1056172) | Cod sursa (job #2544208) | Cod sursa (job #229653)
Cod sursa(job #229653)
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<cassert>
#define pb push_back
#define mkp make_pair
using namespace std;
const int maxn = 400000;
int N,M;
int VER[maxn],NR;
int ANS,NOD;
vector<int> VECT[maxn],VECT1[maxn];
vector<pair<int,pair<int,int> > > VECTMU;
void dfs2(int nod)
{
if (VER[nod])return;
VER[nod] = 1;
for(unsigned int i = 0;i < VECT1[nod].size();++i) dfs2(VECT1[nod][i]);
}
int main()
{
freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
scanf("%d %d\n",&N,&M);
for(int i = 1;i <= M; ++i)
{
int x,y,c;
scanf("%d %d %d",&x,&y,&c);
VECT[x].pb(y);
VECT[y].pb(x);
VECTMU.pb(mkp(c,mkp(x,y)));
}
NR = N;
sort(VECTMU.begin(),VECTMU.end());
NR = N;
for(int i = 0;i < M; ++i)
{
int cost = VECTMU[i].first;
int nod1 = VECTMU[i].second.first;
NOD = VECTMU[i].second.second;
memset(VER,0,sizeof(VER));
dfs2(nod1);
if (!VER[NOD]) {--NR;VECT1[nod1].pb(NOD);VECT1[NOD].pb(nod1);ANS += cost;}
if (NR == 1) break;
}
printf("%d\n",ANS);
return 0;
}