#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using pii = pair<int, int>;
// [town-x, town-y, time, cost, id]
using Edge = array<int, 5>;
struct DSU {
vector<int> g;
DSU(int n) : g(n, -1) {}
int find(int a) {
if (g[a] < 0)
return a;
else
return g[a] = find(g[a]);
}
/**
* If a and b are already in the same set, return false and do nothing.
* Otherwise, merge set a and b into one set and return true.
*/
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (g[a] > g[b]) swap(a, b);
g[a] += g[b];
g[b] = a;
return true;
}
};
/**
* Kruskal's Algorithm to find a MST with given edges and weights. Returns the
* time and cost as pair<int,int> as well as ids of edges of the MST as
* vector<int>.
*/
pair<pii, vector<int>> kruskal(int n, vector<Edge> &edges,
vector<int> &weights) {
sort(begin(edges), end(edges), [&](const Edge &e1, const Edge &e2) {
return weights[e1[4]] < weights[e2[4]];
});
DSU dsu(n);
vector<int> mst;
int t = 0;
int c = 0;
for (Edge &e : edges) {
if (dsu.unite(e[0], e[1])) {
t += e[2];
c += e[3];
mst.push_back(e[4]);
}
}
return {{t, c}, mst};
}
/**
* Calculate the signed area of the triangle ABP. This value is negativ if point
* P is on the right side of vector AB.
*/
ll area(pii A, pii B, pii P) {
pii AB = {B.first - A.first, B.second - A.second};
pii AC = {P.first - A.first, P.second - A.second};
return AB.first * AC.second - AB.second * AC.first;
}
int main() {
int N, M;
cin >> N >> M;
vector<Edge> edges(M);
for (int i = 0; i < M; i++) {
int x, y, t, c;
cin >> x >> y >> t >> c;
edges[i] = {x, y, t, c, i};
}
// The best Minimum Spanning Tree found so far.
vector<int> best_MST;
// The sum of time and cost w.r.t. best_MST.
pii best_V = {1e8, 1e8};
vector<int> current_MST;
pii A, B, P;
// The weights used by Kruskal's Algorithm to determine the MST.
vector<int> weights(M);
// A corresponds to the values of the MST if we only minimize the time
for (int i = 0; i < M; i++) {
weights[edges[i][4]] = edges[i][2];
}
tie(A, best_MST) = kruskal(N, edges, weights);
best_V = A;
// B corresponds to values of the MST if we only minimize the cost
for (int i = 0; i < M; i++) {
weights[edges[i][4]] = edges[i][3];
}
tie(B, current_MST) = kruskal(N, edges, weights);
// If solution B is better than A, update the best solution
if ((ll)B.first * B.second < (ll)A.first * A.second) {
best_V = B;
best_MST = current_MST;
}
// Search recursively for points on lower convex hull of the solution space
stack<pair<pii, pii>> to_search;
to_search.push({A, B});
while (!to_search.empty()) {
tie(A, B) = to_search.top();
to_search.pop();
/*
* Since P is on the right side of vector AB, the signed area is negativ.
* Thus, to maximize the unsigned area of triangle ABP, we should minimize
* this signed value.
*/
for (int i = 0; i < M; i++) {
weights[edges[i][4]] = edges[i][3] * (B.first - A.first) -
edges[i][2] * (B.second - A.second);
}
tie(P, current_MST) = kruskal(N, edges, weights);
/*
* If P is on the left side of vector AB, we can terminate the search
* on this branch. Note that the "left side of vector AB" is the right side
* on the coordinate system.
*/
if (area(A, B, P) >= 0) {
continue;
}
// Compare the V value and update the best result if needed.
if ((ll)P.first * P.second < (ll)best_V.first * best_V.second) {
best_V = P;
best_MST = current_MST;
}
/*
* Search further with the new acquired point P to see if there is another
* point that is on a hyperbola further left than P.
*/
to_search.push({A, P});
to_search.push({P, B});
}
cout << best_V.first << " " << best_V.second << "\n";
sort(begin(edges), end(edges),
[](const Edge &e1, const Edge &e2) { return e1[4] < e2[4]; });
for (int &id : best_MST) {
cout << edges[id][0] << " " << edges[id][1] << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
3 ms |
340 KB |
Output is correct |
| 8 |
Correct |
12 ms |
692 KB |
Output is correct |
| 9 |
Correct |
1 ms |
300 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
4 ms |
212 KB |
Output is correct |
| 15 |
Correct |
3 ms |
300 KB |
Output is correct |
| 16 |
Correct |
46 ms |
356 KB |
Output is correct |
| 17 |
Correct |
49 ms |
360 KB |
Output is correct |
| 18 |
Correct |
56 ms |
340 KB |
Output is correct |
| 19 |
Correct |
419 ms |
668 KB |
Output is correct |
| 20 |
Correct |
450 ms |
668 KB |
Output is correct |
