#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef long double ld;
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()
const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 1e6 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
struct edge{
int a, b, c, t;
ld val;
};
int n, m, st, sc;
vector<edge> v, ans;
vi par, sz;
bool cmp(edge &a, edge &b){
return a.val < b.val;
}
int find(int x){
return par[x] == x ? x : par[x] = find(par[x]);
}
void unite(edge &x){
int a = find(x.a), b = find(x.b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a, b);
sz[a] += sz[b];
par[b] = a;
sc += x.c;
st += x.t;
ans.PB(x);
}
int check(ld rat){
for(int i=0; i<n; i++) par[i] = i, sz[i] = 1;
for(int i=0; i<m; i++) v[i].val = v[i].c * rat + v[i].t * ((ld)1e6 - rat);
sort(v.begin(), v.end(), cmp);
sc = st = 0;
ans.clear();
for(int i=0; i<m; i++) unite(v[i]);
return sc * st;
}
void solve(){
cin >> n >> m;
v.resize(m);
for(int i=0; i<m; i++) cin>> v[i].a >> v[i].b >> v[i].t >> v[i].c;
par.resize(n);
sz.resize(n);
ld lo=0, hi=1e6;
while(abs(lo - hi) > 1e-8){
ld m1 = (2*lo + hi) / 3;
ld m2 = (lo + 2*hi) / 3;
if(check(m1) < check(m2)) hi = m2;
else lo = m1;
}
check(lo);
cout << st << " " << sc << "\n";
for(auto &x : ans) cout << x.a << " " << x.b << "\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tt = 1;
//cin >> tt;
while(tt--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
456 KB |
Output is correct |
| 5 |
Correct |
3 ms |
344 KB |
Output is correct |
| 6 |
Correct |
2 ms |
456 KB |
Output is correct |
| 7 |
Correct |
17 ms |
548 KB |
Output is correct |
| 8 |
Correct |
75 ms |
860 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
456 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
4 ms |
480 KB |
Output is correct |
| 15 |
Correct |
4 ms |
348 KB |
Output is correct |
| 16 |
Correct |
23 ms |
564 KB |
Output is correct |
| 17 |
Correct |
17 ms |
344 KB |
Output is correct |
| 18 |
Correct |
17 ms |
344 KB |
Output is correct |
| 19 |
Correct |
120 ms |
860 KB |
Output is correct |
| 20 |
Correct |
112 ms |
604 KB |
Output is correct |
