//11860 1203
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 205;
using i64 = long long;
using f64 = double;
using pii = pair<int, int>;
using ptx = pair<f64, f64>;
struct Edge {
int u, v, x, y; };
int far[N];
vector<Edge> partans;
vector<Edge> edgs;
int n, m;
pii ans;
static int get_far(int u) {
return (far[u] == -1 ? u : (far[u] = get_far(far[u]))); }
static bool join(int a, int b) {
a = get_far(a);
b = get_far(b);
if (a == b)
return false;
if (rand() % 2)
swap(a, b);
far[a] = b;
return true; }
static pii solve(i64 a, i64 b) {
static vector<Edge> select;
select.clear();
pii ant(0, 0);
memset(far, 0xff, sizeof far);
sort(begin(edgs), end(edgs), [&](const Edge &s, const Edge &t) {
return make_pair(a * s.x + b * s.y, pii(s.u, s.v)) < make_pair(a * t.x + b * t.y, pii(t.u, t.v)); });
for (auto e: edgs) {
if (join(e.u, e.v)) {
select.push_back(e);
ant.x+= e.x;
ant.y+= e.y; } }
if (1LL * ant.x * ant.y < 1LL * ans.x * ans.y) {
partans = select;
ans = ant; }
return ant; }
static i64 ccw(pii a, pii b, pii c) {
return i64(a.x - b.x) * (c.y - b.y) - i64(a.y - b.y) * (c.x - b.x); }
static void divide(pii a, pii b) {
pii mid = solve(b.x - a.x, a.y - b.y);
if (mid == a || mid == b || a == b)
return;
if (ccw(a, b, mid) <= 0)
return;
divide(a, mid);
divide(mid, b); }
int main() {
#ifdef HOME
freopen("timeismoney.in", "r", stdin);
freopen("timeismoney.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
srand(time(NULL));
ans = pii(1e9, 1e9);
cin >> n >> m;
edgs.resize(m);
for (auto &e: edgs)
cin >> e.u >> e.v >> e.x >> e.y;
divide(solve(1, 0), solve(0, 1));
cout << ans.x << ' ' << ans.y << '\n';
for (auto e: partans)
cout << e.u << ' ' << e.v << '\n';
return 0; }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
380 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
3 ms |
376 KB |
Output is correct |
| 8 |
Correct |
8 ms |
504 KB |
Output is correct |
| 9 |
Correct |
2 ms |
256 KB |
Output is correct |
| 10 |
Correct |
2 ms |
372 KB |
Output is correct |
| 11 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 12 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 13 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 14 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 17 |
Incorrect |
4 ms |
424 KB |
Output isn't correct |
| 18 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 19 |
Incorrect |
13 ms |
504 KB |
Output isn't correct |
| 20 |
Incorrect |
12 ms |
504 KB |
Output isn't correct |
