QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#239443 | #6560. Broken Minimum Spanning Tree | Fyind# | TL | 0ms | 3556kb | C++20 | 2.5kb | 2023-11-04 20:43:22 | 2023-11-04 20:43:23 |
Judging History
answer
#include <bits/stdc++.h>
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
#define ls o << 1
#define rs o << 1 | 1
using namespace std;
typedef long long ll;
void solve() {
int n, m;
cin >> n >> m;
vector<pair<pair<int, pair<int, int>>, int>> e(m + 1);
map<pair<int, int>, int> mm;
map<pair<int, int>, int> ee;
vector<set<pair<int, int>>> g(n + 1);
for (int i = 1; i <= m; ++i) {
cin >> e[i].fi.se.fi >> e[i].fi.se.se >> e[i].fi.fi;
e[i].se = i;
if (e[i].fi.se.fi > e[i].fi.se.se)
swap(e[i].fi.se.fi, e[i].fi.se.se);
if (i <= n - 1)
mm[e[i].fi.se] = i, g[e[i].fi.se.fi].insert({e[i].fi.se.se, i}), g[e[i].fi.se.se].insert({e[i].fi.se.fi, i});
}
vector<pair<int, int>> la(n + 1);
function<void(int)> dfs = [&](int u){
// cout << u << '-' << endl;
for (auto [v, i] : g[u])
if (v != la[u].fi) {
int uu = u, vv = v;
if (uu > vv)
swap(uu, vv);
la[v] = {u, ee[{uu, vv}]}, dfs(v);
}
};
sort(e.begin() + 1, e.end());
for (int i = 1; i <= m; ++i)
ee[e[i].fi.se] = i;
vector<pair<int, int>> ans;
for (int i = 1; i <= m; ++i) {
int u = e[i].fi.se.fi, v = e[i].fi.se.se;
if (mm[{u, v}] == e[i].se)
continue;
// cout << u << ',' << v << endl;
dfs(u);
int pos = -1, mx = e[i].fi.fi, cur = v;
while (cur != u) {
// cout << cur << '!' << endl;
if (mx < e[la[cur].se].fi.fi) {
mx = e[la[cur].se].fi.fi, pos = la[cur].se;
}
cur = la[cur].fi;
}
// cout << cur << endl;
// cout << pos << ',' << mx << endl;
if (pos != -1) {
g[e[pos].fi.se.fi].erase({e[pos].fi.se.se, e[pos].se}), g[e[pos].fi.se.se].erase({e[pos].fi.se.fi, e[pos].se});
g[u].insert({v, e[i].se}), g[v].insert({u, e[i].se});
mm.erase(e[pos].fi.se);
mm[e[i].fi.se] = e[i].se;
ans.push_back({e[pos].se, e[i].se});
}
}
cout << ans.size() << '\n';
for (auto [x, y] : ans)
cout << x << ' ' << y << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
#ifdef LLOCAL
freopen("a.in", "r", stdin);
#endif
// int t;
// cin >> t;
// while (t--)
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3556kb
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
Time Limit Exceeded
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