#include <bits/stdc++.h>
using namespace std;
const long long MAXN=200, MAXM=10000;
long long n, m;
long long xe[MAXM], ye[MAXM], te[MAXM], ce[MAXM];
long long link[MAXN], csize[MAXN];
long long tbest=2e18, cbest=1;
vector<long long> bestedges;
bool tcompare(long long x, long long y)
{
if (te[x]<te[y])
return true;
return false;
}
bool ccompare(long long x, long long y)
{
if (ce[x]<ce[y])
return true;
return false;
}
long long find(long long x)
{
if (link[x]==x)
return x;
return link[x]=find(link[x]);
}
void unite(long long x, long long y)
{
if (csize[x]<csize[y])
swap(x, y);
csize[x]=csize[x]+csize[y];
link[y]=x;
return;
}
void makehull(vector<long long> left, vector<long long> right, long long xl, long long yl, long long xr, long long yr)
{
double m=(double)((double)yl-yr)/(xl-xr);
vector<pair<double, long long> > edges;
//cout << xl << ' ' << yl << ' ' << xr << ' ' << yr << '\n';
//cout << m << '\n';
for (long long i=0; i<n-1; i++)
{
long long t=te[left[i]];
long long c=ce[left[i]];
edges.push_back({-m*t+c, left[i]});
}
for (long long i=0; i<n-1; i++)
{
long long t=te[right[i]];
long long c=ce[right[i]];
edges.push_back({-m*t+c, right[i]});
}
sort(edges.begin(), edges.end());
for (long long i=0; i<n; i++)
{
link[i]=i;
csize[i]=1;
}
vector<long long> mid;
long long tsum=0, csum=0;
for (long long i=0; i<(long long)edges.size(); i++)
{
long long x=xe[edges[i].second];
long long y=ye[edges[i].second];
long long t=te[edges[i].second];
long long c=ce[edges[i].second];
if (find(x)==find(y))
continue;
unite(find(x), find(y));
mid.push_back(edges[i].second);
tsum=tsum+t;
csum=csum+c;
}
if (tsum*csum<tbest*cbest)
{
tbest=tsum;
cbest=csum;
bestedges=mid;
}
double k=(double)yl-m*xl;
if (abs((double)csum-m*tsum-k)<(double)1e-3)
return;
sort(mid.begin(), mid.end());
if (mid!=left && mid!=right)
{
makehull(left, mid, xl, yl, tsum, csum);
makehull(mid, right, tsum, csum, xr, yr);
}
return;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (long long i=0; i<m; i++)
cin >> xe[i] >> ye[i] >> te[i] >> ce[i];
long long sorted[m];
for (long long i=0; i<m; i++)
sorted[i]=i;
long long tsum=0, csum=0;
sort(sorted, sorted+m, tcompare);
for (long long i=0; i<n; i++)
{
link[i]=i;
csize[i]=1;
}
vector<long long> tmin;
for (long long i=0; i<m; i++)
{
long long x=xe[sorted[i]];
long long y=ye[sorted[i]];
long long t=te[sorted[i]];
long long c=ce[sorted[i]];
if (find(x)==find(y))
continue;
unite(find(x), find(y));
tmin.push_back(sorted[i]);
tsum=tsum+t;
csum=csum+c;
}
if (tsum*csum<tbest*cbest)
{
tbest=tsum;
cbest=csum;
bestedges=tmin;
}
long long ttemp=tsum;
long long ctemp=csum;
for (long long i=0; i<m; i++)
sorted[i]=i;
sort(sorted, sorted+m, ccompare);
for (long long i=0; i<n; i++)
{
link[i]=i;
csize[i]=1;
}
vector<long long> cmin;
tsum=0;
csum=0;
for (long long i=0; i<m; i++)
{
long long x=xe[sorted[i]];
long long y=ye[sorted[i]];
long long t=te[sorted[i]];
long long c=ce[sorted[i]];
if (find(x)==find(y))
continue;
unite(find(x), find(y));
cmin.push_back(sorted[i]);
tsum=tsum+t;
csum=csum+c;
}
if (tsum*csum<tbest*cbest)
{
tbest=tsum;
cbest=csum;
bestedges=cmin;
}
makehull(tmin, cmin, ttemp, ctemp, tsum, csum);
cout << tbest << ' ' << cbest << '\n';
for (long long i=0; i<n-1; i++)
{
long long x=xe[bestedges[i]];
long long y=ye[bestedges[i]];
cout << x << ' ' << y << '\n';
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
6 ms |
860 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Runtime error |
80 ms |
65536 KB |
Execution killed with signal 9 |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 15 |
Incorrect |
4 ms |
604 KB |
Output isn't correct |
| 16 |
Incorrect |
10 ms |
712 KB |
Output isn't correct |
| 17 |
Incorrect |
10 ms |
604 KB |
Output isn't correct |
| 18 |
Incorrect |
11 ms |
604 KB |
Output isn't correct |
| 19 |
Incorrect |
14 ms |
1004 KB |
Output isn't correct |
| 20 |
Incorrect |
13 ms |
856 KB |
Output isn't correct |
