#include<bits/stdc++.h>
using namespace std;
int n,m;
pair<pair<int,int>,pair<int,int>> edges[10005];
double cst;
bool caz;
int father[300];
int siz[300];
int gas(int x)
{
if(x!=father[x])
father[x]=gas(father[x]);
return father[x];
}
void unite(int x, int y)
{
x = gas(x);
y = gas(y);
if(x==y)
return;
if(siz[x]<siz[y])
swap(x,y);
father[y]=x;
siz[x]+=siz[y];
}
double calc(pair<pair<int,int>,pair<int,int>> x)
{
if(caz) return (double)x.first.first * cst + (double)x.first.second;
else return (double)x.first.first + (double)x.first.second * cst;
}
bool cmp(pair<pair<int,int>,pair<int,int>> x, pair<pair<int,int>,pair<int,int>> y)
{
return calc(x) < calc(y);
}
int best0,best1;
vector<pair<int,int>> sol;
vector<pair<int,int>> cur;
long long solve(double x)
{
cst = x;
cur.clear();
sort(edges,edges+m,cmp);
int sum0=0,sum1=0;
for(int i=0;i<n;i++)
father[i]=i,siz[i]=1;
for(int i=0;i<m;i++)
{
if(gas(edges[i].second.first)!=gas(edges[i].second.second))
{
unite(edges[i].second.first,edges[i].second.second);
cur.push_back(edges[i].second);
sum0+=edges[i].first.first;
sum1+=edges[i].first.second;
}
}
if(best0==-1 || 1LL*sum0*sum1 < 1LL*best0*best1)
{
sol = cur;
best0=sum0;
best1=sum1;
}
return best0*best1;
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
for(int i=0;i<m;i++)
{
cin>>edges[i].second.first>>edges[i].second.second>>edges[i].first.first>>edges[i].first.second;
}
double st,dr,mij1,mij2;
best0=-1;
for(int x=1;x<=2600000;x+=5000)///it1
{
caz=1;
st = x;
dr = x+999;
for(int i=0;i<100;i++)///it2
{
mij1=st+(dr-st)/3;
mij2=mij1+(dr-st)/3;
if(solve(mij1)<solve(mij2))
dr=mij2;
else
st=mij1;
}
caz=0;
st = x;
dr = x+999;
for(int i=0;i<100;i++)
{
mij1=st+(dr-st)/3;
mij2=mij1+(dr-st)/3;
if(solve(mij1)<solve(mij2))
dr=mij2;
else
st=mij1;
}
}
cout<<best0<<" "<<best1<<"\n";
for(int i=0;i<sol.size();i++)
cout<<sol[i].first<<" "<<sol[i].second<<"\n";
return 0;
}
/**
it1 * it2 <= 10000
*/
Compilation message
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int i=0;i<sol.size();i++)
| ~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1644 ms |
456 KB |
Output is correct |
| 2 |
Correct |
92 ms |
460 KB |
Output is correct |
| 3 |
Correct |
135 ms |
348 KB |
Output is correct |
| 4 |
Correct |
520 ms |
448 KB |
Output is correct |
| 5 |
Execution timed out |
2021 ms |
344 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2040 ms |
348 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2089 ms |
504 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2065 ms |
592 KB |
Time limit exceeded |
| 9 |
Correct |
86 ms |
348 KB |
Output is correct |
| 10 |
Correct |
238 ms |
348 KB |
Output is correct |
| 11 |
Incorrect |
138 ms |
344 KB |
Output isn't correct |
| 12 |
Incorrect |
533 ms |
448 KB |
Output isn't correct |
| 13 |
Incorrect |
529 ms |
444 KB |
Output isn't correct |
| 14 |
Execution timed out |
2063 ms |
348 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2054 ms |
348 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2052 ms |
344 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2033 ms |
344 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2059 ms |
348 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2005 ms |
600 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2012 ms |
600 KB |
Time limit exceeded |
