#include<bits/stdc++.h>
#include <cmath>
#include<fstream>
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const int mxn = 100000, sq = 400;
const ll inf = 1e13, mod = 998244353, pr = 37;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
#define ull unsigned long long
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll INF = numeric_limits<ll>::max() / 4;
#define vi vector<int>
struct E{
ll u, v, w, id;
bool operator <(const E &other){
return(w < other.w);
}
};
int n, m;
ll eu[mxn + 1], ev[mxn + 1], et[mxn + 1], ec[mxn + 1];
int pa[mxn + 1];
struct P{
ll t, c;
P(){
t = c = 0;
}
};
vector<P>candidates;
vt<int>ansedge;
ll ans = inf;
P anspoint;
int fp(int u){
if(pa[u] < 0)return(u);
return(pa[u] = fp(pa[u]));
}
bool unon(int u, int v){
u = fp(u); v = fp(v);
if(u == v)return(0);
if(-pa[u] < -pa[v])swap(u, v);
pa[u] += pa[v]; pa[v] = u;
return(1);
}
P find_mst(ll coef_c, ll coef_t){
//cout << coef_c << " " << coef_t << " ";
vt<E>edge;
for(int i = 0; i < m; i++){
edge.pb({eu[i], ev[i], et[i] * coef_t + ec[i] * coef_c, i});
}
sort(ALL(edge));
for(int i = 0; i < n; i++)pa[i] = -1;
P res;
vt<int>idedge;
for(auto [u, v, w, i]: edge){
if(unon(u, v)){
res.t += et[i]; res.c += ec[i];
idedge.pb(i);
}
}
//cout << res.t << " " << res.c << "\n";
if(res.t * res.c < ans){
ans = res.t * res.c; ansedge = idedge;
anspoint = res;
}
return(res);
}
void dnc(P l, P r){
P mid = find_mst(l.t - r.t, r.c - l.c);
if(mid.c == l.c && mid.t == l.t)return;
if(mid.c == r.c && mid.t == r.t)return;
dnc(l, mid); dnc(mid, r);
}
void solve(){
cin >> n >> m;
for(int i = 0; i < m; i++){
cin >> eu[i] >> ev[i] >> et[i] >> ec[i];
}
P upper_point = find_mst(1, 0), lower_point = find_mst(0, 1);
dnc(upper_point, lower_point);
cout << anspoint.t << " " << anspoint.c << "\n";
for(auto i: ansedge){
cout << eu[i] << " " << ev[i] << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tt; tt = 1;
while(tt--){
solve();
}
return(0);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |