1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
| #include <bits/stdc++.h> #define V vector #define Vi vector<int> #define sz(a) ((int)a.size()) #define fi first #define se second #define Int pair<int, int> #define Inf ((int)1e9) #define pb push_back #define ins insert #define For(i, x, y) for (auto i = (x); i <= (y); i++) #define Rep(i, x, y) for (auto i = (x); i >= (y); i--) #define all(a) a.begin(), a.end() #define IO(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout); using namespace std;
#define int long long
struct Edge { int x, y, z1, z2, v; };
struct Ace_taffy { Vi f; Ace_taffy(int n) : f(n + 5) { For(i, 1, n) f[i] = i; } int get(int k) { return f[k] == k ? k : f[k] = get(f[k]); } void merge(int x, int y) { f[get(x)] = get(y); } };
signed main() { #ifndef ONLINE_JUDGE IO(1); #endif ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m; cin >> n >> m;
V<Edge> a(m + 5); For(i, 1, m) cin >> a[i].x >> a[i].y >> a[i].z1 >> a[i].z2;
int ans1 = Inf, ans2 = Inf; auto solve = [&](int x, int y) { For(i, 1, m) a[i].v = a[i].z1 * x + a[i].z2 * y; sort(&a[1], &a[m + 1], [&](Edge x, Edge y) { return x.v < y.v; }); Ace_taffy tr(n); int res1 = 0, res2 = 0; For(i, 1, m) { int x = tr.get(a[i].x), y = tr.get(a[i].y); if (x != y) tr.merge(x, y), res1 += a[i].z1, res2 += a[i].z2; } if (res1 * res2 < ans1 * ans2 || (ans1 * ans2 == res1 * res2 && res1 < ans1)) ans1 = res1, ans2 = res2; return (Int){res1, res2}; };
auto work = [&](auto lf, Int L, Int R) -> void { Int M = solve(L.se - R.se, R.fi - L.fi); if (M == L || M == R || M.fi < L.fi || M.fi > R.fi || M.se < R.se || M.se > L.se) return; lf(lf, L, M), lf(lf, M, R); };
Int L = solve(1, 0), R = solve(0, 1); work(work, L, R); cout << ans1 << ' ' << ans2 << '\n'; }
|