#include <bits/stdc++.h>
using namespace std;
const int MAXN=200, MAXM=10000;
int n, m;
int xe[MAXM], ye[MAXM], te[MAXM], ce[MAXM];
int link[MAXN], csize[MAXN];
long long tbest=2e18, cbest=1;
vector<int> bestedges;
bool tcompare(int x, int y)
{
if (te[x]<te[y])
return true;
return false;
}
bool ccompare(int x, int y)
{
if (ce[x]<ce[y])
return true;
return false;
}
int find(int x)
{
if (link[x]==x)
return x;
return link[x]=find(link[x]);
}
void unite(int x, int y)
{
if (csize[x]<csize[y])
swap(x, y);
csize[x]=csize[x]+csize[y];
link[y]=x;
return;
}
void makehull(vector<int> left, vector<int> right, int xl, int yl, int xr, int yr)
{
double m=(double)((double)yl-yr)/(xl-xr);
vector<pair<double, int> > edges;
//cout << xl << ' ' << yl << ' ' << xr << ' ' << yr << '\n';
//cout << m << '\n';
for (int i=0; i<n-1; i++)
{
int t=te[left[i]];
int c=ce[left[i]];
edges.push_back({-m*t+c, left[i]});
}
for (int i=0; i<n-1; i++)
{
int t=te[right[i]];
int c=ce[right[i]];
edges.push_back({-m*t+c, right[i]});
}
sort(edges.begin(), edges.end());
for (int i=0; i<n; i++)
{
link[i]=i;
csize[i]=1;
}
vector<int> mid;
long long tsum=0, csum=0;
for (int i=0; i<(int)edges.size(); i++)
{
int x=xe[edges[i].second];
int y=ye[edges[i].second];
int t=te[edges[i].second];
int 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(m*tsum+csum-k)<1e9)
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 (int i=0; i<m; i++)
cin >> xe[i] >> ye[i] >> te[i] >> ce[i];
int sorted[m];
for (int i=0; i<m; i++)
sorted[i]=i;
long long tsum=0, csum=0;
sort(sorted, sorted+m, tcompare);
for (int i=0; i<n; i++)
{
link[i]=i;
csize[i]=1;
}
vector<int> tmin;
for (int i=0; i<m; i++)
{
int x=xe[sorted[i]];
int y=ye[sorted[i]];
int t=te[sorted[i]];
int 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;
}
int ttemp=tsum;
int ctemp=csum;
for (int i=0; i<m; i++)
sorted[i]=i;
sort(sorted, sorted+m, ccompare);
for (int i=0; i<n; i++)
{
link[i]=i;
csize[i]=1;
}
vector<int> cmin;
tsum=0;
csum=0;
for (int i=0; i<m; i++)
{
int x=xe[sorted[i]];
int y=ye[sorted[i]];
int t=te[sorted[i]];
int 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 (int i=0; i<n-1; i++)
{
int x=xe[bestedges[i]];
int y=ye[bestedges[i]];
cout << x << ' ' << y << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 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 |
3 ms |
604 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 12 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 13 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 14 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 15 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 16 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 17 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 18 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 19 |
Incorrect |
3 ms |
604 KB |
Output isn't correct |
| 20 |
Incorrect |
3 ms |
604 KB |
Output isn't correct |
