#include <bits/stdc++.h>
using namespace std;
struct wow
{
long double x,y,bani,timp,constanta;
}v[10005];
bool compare (wow a,wow b)
{
return a.constanta<b.constanta;
}
int tata[205],sol[2005],q,rang[205],sumbani,sumtimp;
int n,m,i;
int parinte (int x)
{
if (tata[x]!=x)
{
return parinte(tata[x]);
}
return x;
}
void uneste (int x,int y)
{
x=parinte(x);
y=parinte(y);
if (rang[x]<rang[y])
{
tata[x]=y;
}
else
if (rang[x]>rang[y])
{
tata[y]=x;
}
else
{
tata[y]=x;
rang[x]++;
}
}
long double MAX=1e6;
int val(long double mij)
{
int i;
for (i=1;i<=m;i++)
{
v[i].constanta=v[i].timp*mij+v[i].bani*(MAX-mij);
}
sort (v+1,v+m+1,compare);
for (i=1;i<=n;i++)
{
tata[i]=i;
rang[i]=1;
}
q=0;
sumbani=0;
sumtimp=0;
for (i=1;i<=m;i++)
{
if (parinte(v[i].x)!=parinte(v[i].y))
{
uneste(v[i].x,v[i].y);
sumbani=sumbani+v[i].bani;
sumtimp=sumtimp+v[i].timp;
sol[++q]=i;
}
}
return sumbani*sumtimp;
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0);
#ifdef HOME
ifstream cin("timeismoney.in");
ofstream cout("timeismoney.out");
#endif // HOME
cin>>n>>m;
for (i=1;i<=m;i++)
{
cin>>v[i].x>>v[i].y>>v[i].timp>>v[i].bani;
v[i].x++;
v[i].y++;
}
long double st=1,dr=MAX-1;
while (dr-st>=1e-6)
{
long double m1=st+(dr-st)/3;
long double m2=dr-(dr-st)/3;
if (val(m1)<val(m2))
{
dr=m2;
}
else
{
st=m1;
}
}
val(st);
cout<<sumtimp<<" "<<sumbani<<'\n';
for (i=1;i<=q;i++)
{
cout<<v[sol[i]].x-1<<" "<<v[sol[i]].y-1<<'\n';
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
17 ms |
384 KB |
Output is correct |
6 |
Correct |
16 ms |
384 KB |
Output is correct |
7 |
Correct |
71 ms |
512 KB |
Output is correct |
8 |
Correct |
351 ms |
1272 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
4 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
14 ms |
384 KB |
Output is correct |
15 |
Correct |
17 ms |
440 KB |
Output is correct |
16 |
Correct |
79 ms |
512 KB |
Output is correct |
17 |
Correct |
74 ms |
512 KB |
Output is correct |
18 |
Correct |
87 ms |
512 KB |
Output is correct |
19 |
Correct |
413 ms |
1152 KB |
Output is correct |
20 |
Correct |
476 ms |
1180 KB |
Output is correct |