Buna ziua! Va rog sa ma ajutati sa rezolv aceasta problema :
Țăranul Ion are în livada sa N pomi, fiecare cu v mere. Între pomi există N-1 cărări, astfel încât între oricare doi pomi să existe un singur drum, alcătuit eventual din mai multe cărări. El vrea să adune merele din livadă, dar pentru că nu are foarte mult timp, el va aduna merele doar dintr-o parte din pomi.
Ion porneste din pomul lui preferat, pomul 1, si se deplasează spre unul din vecinii lui. Pentru că nu este foarte inteligent, atunci când Ion se află la un pom, el se va deplasa către pomul vecin care are cele mai multe mere, fără să ia în calcul ceilalti meri din livadă. Dacă doi pomi au acelasi număr de mere, atunci Ion se va deplasa spre pomul cu numărul de ordine mai mic.
Ajutati-l pe Ion să afle câte mere va aduna folosind metoda sa!
Am incercat sa o rezolv dar nu am reusit. Am intrebat profesoara si a spus ca se rezolva prin algoritmul lui Kruskal. Eu nu vad cum ar putea sa se rezolve aceasta problema prin acest algoritm…
ce am incercat eu..
int citire()
{ifstream f(„livada.txt”);
f>>n;
cout<<„Livada este formata din „<<n<<” copaci”<<endl;
for(i=1;i<=n;i++)
{f>>v;
cout<<„Copacul „<<i<<” are „;
cout<<v<<” mere „<<endl;;}
for(j=1;j<=n-1;j++)
{f>>x>>y;
l[x][y]=l[y][x]=1;
}
return 0;
}
int afisare()
{int i,j;
cout<<„Exista carare intre pomii : „;
for(i=1;i<=n;i++)
{for(j=1;j<=i;j++)
if (l[j]==1)
cout<<j<<„-„<<i<<endl;
}
return 0;
}
int suma()
{int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
{if(l[j]==1 && l[j+1]==1)
{if(v[j]>v[j+1])
m=m+v[j];
else
m=m+v[j+1];}
}
return m;
}
int main()
{citire();
afisare();
cout<<„Ion culege „<<suma()<<” mere.”;
return 0;
}