#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 2e6 + 5, MOD = 1e9 + 7, INF = 1e18;
int n, m;
struct DSU{
vector<int> par, sz;
int n;
DSU(int _n = 0){
init(_n);
}
void init(int _n){
n = _n; par.resize(n + 1, 0), sz.resize(n + 1, 0);
for(int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
}
int root(int x){
return par[x] = (x == par[x] ? x : root(par[x]));
}
bool unite(int x, int y){
x = root(x), y = root(y);
if(x != y){
if(sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y], par[y] = x;
return true;
}
return false;
}
};
struct Edge{
int u, v, t, c;
};
struct st{
int st = 0, sc = 0;
vector<int> eid;
};
vector<Edge> e;
st optimal(int a, int b){
vector<int> id(m); iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int x, int y){
return e[x].t * a + e[x].c * b < e[y].t * a + e[y].c * b;
});
st ans;
DSU tmp(n);
ans.eid.reserve(n);
for(int x : id){
if(tmp.unite(e[x].u, e[x].v)){
ans.eid.push_back(x);
ans.st += e[x].t, ans.sc += e[x].c;
}
}
return ans;
}
vector<st> v;
void dnc(st l, st r){
int na = r.st - l.st, nb = r.sc - l.sc;
st nw = optimal(-nb, na);
if(nw.st == l.st && nw.sc == l.sc) return;
if(nw.st == r.st && nw.sc == r.sc) return;
int na1 = nw.st - l.st, nb1 = nw.sc - l.sc;
if(na1 * nb == nb1 * na) return;
v.push_back(nw);
dnc(l, nw), dnc(nw, r);
}
void solve(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
int u, v, t, c; cin >> u >> v >> t >> c;
e.push_back({u, v, t, c});
}
st m1 = optimal(1, 0);
st m2 = optimal(0, 1);
v.reserve(300);
v.push_back(m1);
v.push_back(m2);
dnc(m1, m2);
int ans = INF;
st best;
for(st cur : v){
if(ans > cur.st * cur.sc){
ans = cur.st * cur.sc;
best = cur;
}
}
cout << best.st << ' ' << best.sc << '\n';
for(int id : best.eid){
cout << e[id].u << ' ' << e[id].v << '\n';
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
while(t--){
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |