QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#239443#6560. Broken Minimum Spanning TreeFyind#TL 0ms3556kbC++202.5kb2023-11-04 20:43:222023-11-04 20:43:23

Judging History

你现在查看的是最新测评结果

  • [2023-11-04 20:43:23]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3556kb
  • [2023-11-04 20:43:22]
  • 提交

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

output:


result: