QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#134468 | #6560. Broken Minimum Spanning Tree | Noobie_99# | WA | 1ms | 3520kb | C++20 | 1.6kb | 2023-08-03 20:28:26 | 2023-08-03 20:28:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define tsolve int t; cin >> t; while(t--) solve
#define debug(x) cerr << __LINE__ << ": "#x" = " << (x) << endl
#define nl '\n'
#define all(x) ::begin(x), ::end(x)
#define sz(x) (int)::size(x)
using ll = long long;
using ld = long double;
struct edge {
ll from, to, weight, id;
};
ll n, m;
vector<vector<edge>> adj;
vector<edge> edges;
vector<bool> in_tree;
pair<ll, ll> max_weight(ll c, ll f, ll t, ll id = -1, ll w = 0) {
if (c == t) {
return { w, id };
}
for (edge e : adj[c]) {
if (e.to == f) continue;
if (!in_tree[e.id]) continue;
auto [rw, rid] = max_weight(e.to, c, t, e.id, e.weight);
if (rw == 0) continue;
if (w > rw) return { w, id };
else return { rw, rid };
}
return { 0, -1 };
}
void solve() {
cin >> n >> m;
adj.resize(n);
in_tree.resize(n);
for (ll i = 0; i < m; ++i) {
ll u, v, w;
cin >> u >> v >> w;
--u; --v;
adj[u].push_back({ u, v, w, i });
adj[v].push_back({ v, u, w, i });
edges.push_back({ u, v, w, i });
in_tree[i] = i < n - 1;
}
sort(all(edges), [](edge x, edge y) {
return x.weight < y.weight;
});
vector<pair<ll, ll>> res;
for (edge e : edges) {
if (in_tree[e.id]) continue;
auto [rw, rid] = max_weight(e.from, e.from, e.to);
if (rw < e.weight) continue;
in_tree[rid] = false;
in_tree[e.id] = true;
res.push_back({ rid, e.id });
}
cout << ssize(res) << nl;
for (auto [u, v] : res) {
cout << (u + 1) << ' ' << (v + 1) << nl;
}
}
int main() {
cin.tie(0)->sync_with_stdio(false);
cout << setprecision(16);
solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3476kb
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: 1ms
memory: 3520kb
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:
5 2 7 5 8 1 2 4 5 3 6
result:
FAIL participant's plan is better than jury!