//Wa of course, please give me ac !!! im begging u compiler-sama, have mercy on my poor code !
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define ld long double
#define endl '\n'
#define eb emplace_back
#define em emplace
#define pb push_back
#define pf push_front
#define pp pop_back
#define fr first
#define sc second
#define sz size
const ll mm = 10010;
const ll mx = 205 ;
ll p[mx];
ll f(ll x) {
return p[x] == x ? x : p[x] = f(p[x]);
}
bool un(ll a , ll b) {
ll ra = f(a) , rb = f(b) ;
if(ra == rb) return false ;
p[rb] = ra ;
return true ;
}
ll n , m ;
array<ll , 5> ed[mm] ;
ll bv = 1e18 ,bt , bc;
vector<pair<ll , ll>> be;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0) ; cout.tie(0);
cin >> n >> m;
for(ll i = 0 ; i < m ; i++) {
cin >> ed[i][3] >> ed[i][4] >> ed[i][1] >> ed[i][2] ;
ed[i][0] = ed[i][1] *ed[i][2];
}
sort(ed , ed + m);
for(ll i = 0 ; i < m ;i++){
}
for (ll i = 0; i < m; i++) {
for(ll j = 0 ; j < n ;j++) p[j] = j ;
ll cnt = 0 , ts = 0 , cs = 0;
vector <pair<ll , ll>> ch ;
for(ll j = i ; j <m ;j++) {
ll u = ed[j][3], v = ed[j][4];
ll t = ed[j][1], c = ed[j][2];
if(un(u ,v)){
ts += t;
cs += c ;
ch.eb(u , v) ;
cnt++ ;
if(cnt == n -1) break ;
}
}
if(cnt == n - 1) {
ll vl = ts * cs ;
if(vl < bv) {
bv = vl ;
bt = ts ;
bc = cs ;
be = ch ;
}
}
}
cout << bt <<" " << bc << endl;
for(auto [u, v] : be) cout << u << " " << v << endl;
return 0 ;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |