#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
array<int, 4> e[N];
struct DSU {
int p[N], sz[N];
void init(int n) {
fill(sz+1, sz+n+1, 1);
iota(p+1, p+n+1, 1);
}
int get(int u) {
if (u == p[u]) return u;
return p[u] = get(p[u]);
}
bool unite(int u, int v) {
u = get(u), v = get(v);
if (u == v) return 0;
if (sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v], p[v] = u;
return 1;
}
} D;
int n, m;
int A, B;
long long mn = 1e12;
void solve(int x1, int y1, int x2, int y2) {
// cout << x1 << ' ' << y1 << "|" << x2 << ' ' << y2 << '\n';
int a = y1 - y2, b = x2 - x1;
sort(e+1, e+m+1, [&](array<int, 4> &x, array<int, 4> &y){
return a * x[2] + b * x[3] < a * y[2] + b * y[3];
});
D.init(n);
int xo = 0, yo = 0;
for (int i = 1; i <= m; ++i) {
// if (a == 226) cout << e[i][0] << ' ' << e[i][1] << ' ' << e[i][2] << ' ' << e[i][3] << ' ' << a * e[i][2] + b * e[i][3] << '\n';
if (D.unite(e[i][0], e[i][1])) xo += e[i][2], yo += e[i][3];
}
// cout << x1 << 't' << y1 << "|" << x2 << ' ' << y2 << ' ' << xo << ' ' << yo << ' ' << a << ' ' << b << endl;
if (xo * 1LL * yo < mn) A = a, B = b, mn = xo * 1LL * yo;
if (a * x1 + b * y1 == a * xo + b * yo) return;
solve(x1, y1, xo, yo), solve(xo, yo, x2, y2);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; ++i) cin >> e[i][0] >> e[i][1] >> e[i][2] >> e[i][3];
for (int i = 1; i <= m; ++i) e[i][0]++, e[i][1]++;
D.init(n);
sort(e+1, e+m+1, [&](array<int, 4> &x, array<int, 4> &y){
return x[2] < y[2];
});
int c1 = 0, t1 = 0, c2 = 0, t2 = 0;
for (int i = 1; i <= m; ++i) {
// cout << e[i][0] << ' ' << e[i][1] << ' ' << e[i][2] << ' ' << e[i][3] << '\n';
if (D.unite(e[i][0], e[i][1])) {
c1 += e[i][2], t1 += e[i][3];
}
}
D.init(n);
sort(e+1, e+m+1, [&](array<int, 4> &x, array<int, 4> &y){
return x[3] < y[3];
});
for (int i = 1; i <= m; ++i) {
if (D.unite(e[i][0], e[i][1])) c2 += e[i][2], t2 += e[i][3];
}
// cout << c1 << ' ' << t1 << ' ' << c2 << ' ' << t2 << endl;
solve(c1, t1, c2, t2);
// cout << A << ' ' << B << ' ' << mn << '\n';
sort(e+1, e+m+1, [&](array<int, 4> &x, array<int, 4> &y){
return A * x[2] + B * x[3] < A * y[2] + B * y[3];
});
vector<array<int, 2>> ans;
int C = 0, T = 0;
D.init(n);
for (int i = 1; i <= m; ++i) {
if (D.unite(e[i][0], e[i][1])) C += e[i][2], T += e[i][3], ans.push_back({e[i][0], e[i][1]});
}
cout << C << ' ' << T << '\n';
for (auto [u, v] : ans) cout << u-1 << ' ' << v-1 << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |