Cod sursa(job #744977)

Utilizator tibi9876Marin Tiberiu tibi9876 Data 10 mai 2012 11:35:53
Problema A+B Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
using namespace std;

struct st
{
long long x,y,z;
};

long long t[10],x,i,n,p,q,nr,k,m,s,j,inf;
vector <long long> a[10],b[10];
st v[10];

bool cmp(st a, st b)
{
return a.z>b.z;
}

int main()
{
freopen("adunare.in","r",stdin);
freopen("adunare.out","w",stdout);
n=3;m=2;
for (i=1;i<=m;i++)
{
cin >> x;
a[i].push_back(i+1);
b[i].push_back(x);
a[i+1].push_back(i);
b[i+1].push_back(x);
}
a[1].push_back(3);
b[1].push_back(-1);
a[3].push_back(1);
b[3].push_back(-1);
for (i=1;i<=n;i++)
for (j=0;j<a[i].size();j++)
{
k++;
v[k].x=i;
v[k].y=a[i][j];
v[k].z=b[i][j];
}
sort(v+1,v+k+1,cmp);
for (i=1;i<=n;i++)
t[i]=i;
for (i=1;(i<=k) && (nr<n);i++)
{
p=v[i].x;
q=v[i].y;
while (p!=t[p])
p=t[p];
while (q!=t[q])
q=t[q];
if (p!=q)
{
t[p]=q;
nr++;
s+=v[i].z;
}
}
cout << s;
return 0;
}