QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#240976 | #6560. Broken Minimum Spanning Tree | MovingUp# | WA | 0ms | 3628kb | C++14 | 2.7kb | 2023-11-05 21:32:51 | 2023-11-05 21:32:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct edge {
int id;
int u, v, w;
bool operator<(const edge &o) const { return w < o.w; }
};
struct dsu {
vector<int> parent, subtree;
void init(int n) {
parent.resize(n);
subtree.resize(n);
for (int i = 0; i < n; i++) {
subtree[i] = 1;
parent[i] = i;
}
}
int findParent(int x) {
if (parent[x] == x)
return x;
else {
parent[x] = findParent(parent[x]);
return parent[x];
}
}
void unite(int parX, int parY) {
if (subtree[parX] < subtree[parY]) {
parent[parX] = parY;
subtree[parY] += subtree[parX];
} else {
parent[parY] = parX;
subtree[parX] += subtree[parY];
}
}
};
int64_t findMst(int n, const vector<edge> &edges, int edgeId) {
dsu d;
d.init(n);
int64_t ans = 0;
for (auto e : edges) {
if (e.id == edgeId) {
ans += e.w;
d.unite(e.u, e.v);
}
}
for (auto e : edges) {
if (e.id == edgeId) {
continue;
}
int parX = d.findParent(e.u);
int parY = d.findParent(e.v);
if (parX != parY) {
ans += e.w;
d.unite(parX, parY);
}
}
return ans;
}
int findReplacement(int n, const vector<edge> &edges, vector<bool>& forced) {
dsu d;
d.init(n);
for (auto e : edges) {
if (forced[e.id]) {
d.unite(e.u, e.v);
}
}
for (auto e : edges) {
if (forced[e.id]) {
continue;
}
int parX = d.findParent(e.u);
int parY = d.findParent(e.v);
if (parX != parY) {
return e.id;
}
}
assert(false);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<edge> edges(m);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
u--;
v--;
edges[i] = {i, u, v, w};
}
sort(edges.begin(), edges.end());
int64_t globalMst = findMst(n, edges, -1);
vector<bool> keep(n - 1, false);
for (int i = 0; i < n - 1; i++) {
int64_t currMst = findMst(n, edges, i);
if (currMst == globalMst) {
keep[i] = true;
}
}
dsu d;
d.init(n);
vector<bool> forced(m);
vector<int> removals;
for (int i = 0; i < n - 1; i++) {
forced[i] = true;
if (!keep[i]) {
removals.push_back(i);
}
}
vector<pair<int, int>> changes;
while (!removals.empty()) {
int id = removals.back();
removals.pop_back();
forced[id] = false;
int replacement = findReplacement(n, edges, forced);
forced[replacement] = true;
changes.push_back({id, replacement});
}
cout << changes.size() << endl;
for (auto [x, y] : changes) {
cout << x + 1 << " " << y + 1 << endl;
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
input:
4 4 1 2 10 2 3 3 3 4 1 1 4 4
output:
1 1 4
result:
ok correct!
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3628kb
input:
6 8 1 2 10 2 3 10 3 4 10 4 5 10 5 6 10 6 1 10 1 3 1 4 6 1
output:
0
result:
FAIL participant's MST is better than jury!