Pagini recente » Istoria paginii utilizator/chiar_nimeni | Cod sursa (job #1815417) | Cod sursa (job #1331133) | Cod sursa (job #3204485) | Cod sursa (job #930728)
Cod sursa(job #930728)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
int n,m,i,j,k,tata[32001],c[32001],min1,niv[32001],m1,m2,A,B,C,D,x,y,nr;
struct muchie
{
int x,y,cost;
};
muchie a[32001];
int detniv(int x)
{
if(x==tata[x])
return 0;
detniv(tata[x]);
niv[x]=niv[ tata[x] ]+1;
}
int det(int x)
{
while(x!=tata[x])
x=tata[x];
return x;
}
bool cmp(muchie a, muchie b)
{
return a.cost>b.cost;
}
int main()
{
ifstream f("atac.in");
ofstream g("atac.out");
f>>n>>m>>k;
for(i=2;i<=n;++i)
{
a[i-1].x=i;
f>>a[i-1].y>>a[i-1].cost;
}
for(i=1;i<=n;++i)
tata[i]=i;
sort(a+1,a+n,cmp);
for(i=1;i<n;++i)
{
m1=det(a[i].x);
m2=det(a[i].y);
if(m1!=m2)
{tata[m1]=m2;
c[m1]=a[i].cost;}
}
for(i=1;i<=n;++i)
if(!niv[i])
detniv(i);
f>>m1>>m2>>A>>B>>C>>D;
while(m--)
{
x=m1;
y=m2;
min1=1<<20;
while(niv[m1]>niv[m2])
{
min1=min(min1,c[m1]);
m1=tata[m1];
}
while(niv[m2]>niv[m1])
{
min1=min(min1,c[m2]);
m2=tata[m2];
}
while(m1!=m2)
{
min1=min(min1,min(c[m1],c[m2]));
m1=tata[m1];
m2=tata[m2];
}
if(min1==1<<20)
min1=0;
if(m<k)
g<<min1<<'\n';
m1=(x*A+y*B)%n+1;
m2=(y*C+min1*D)%n+1;
}
}