QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#241423#6560. Broken Minimum Spanning TreeMtaylorWA 0ms18036kbC++203.4kb2023-11-06 06:13:482023-11-06 06:13:49

Judging History

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

  • [2023-11-06 06:13:49]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:18036kb
  • [2023-11-06 06:13:48]
  • 提交

answer

// Mtaylor
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define endl '\n';
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
    cerr << ' ' << H;
    dbg_out(T...);
}
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
typedef long long ll;
const int N = 3e5 + 5;
const int E = 1e6 + 5;

#define neig(u, v, e, g) \
    for (int e = g.head[u], v; ~e && ((v = g.to[e]), 1); e = g.nxt[e])

class ADJ {
   public:
    int head[E], to[E], nxt[E], n, edgcnt = 0;
    int cst[E];

    void addEdge(int a, int b, int c = 0) {
        nxt[edgcnt] = head[a];
        head[a] = edgcnt;
        to[edgcnt] = b;
        cst[edgcnt] = c;
        edgcnt++;
    }

    void addBiEdge(int a, int b, int c = 0) {
        addEdge(a, b, c);
        addEdge(b, a, c);
    }
    void init(int _n) {
        n = _n;
        memset(head, -1, n * sizeof(head[0]));
        edgcnt = 0;
    }
} adj, adj2;

struct DSUGraph {
    vector<int> id, sz;
    void init(int n) {
        id.assign(n, 0);
        sz.assign(n, 0);
        for (int i = 0; i < n; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }
    int getid(int u) { return (u == id[u] ? u : id[u] = getid(id[u])); }
    bool sameSet(int u, int v) { return getid(u) == getid(v); }
    void uni(int u, int v) {
        v = getid(v);
        u = getid(u);
        if (u == v) return;
        id[u] = v;
        sz[v] += sz[u];
    }
} dsu;
int u[N], v[N], w[N];
int n, m;
int target;
int r = 0;
void dfs(int u, int cur = 0, int p = -1) {
    if (u == target) {
        r = cur;
        return;
    }
    neig(u, v, e, adj) {
        if (v == p) continue;
        dfs(v, max(cur, adj.cst[e]), u);
    }
}

bool ok[N];
bool needed[N];
void test_case() {
    cin >> n >> m;
    adj.init(n);
    vector<int> ord;
    for (int i = 0; i < m; i++) {
        cin >> u[i] >> v[i] >> w[i];
        --u[i], --v[i];
        ord.pb(i);
    }
    sort(all(ord), [](int &x, int &y) { return w[x] < w[y]; });
    dsu.init(n);
    for (auto &i : ord) {
        if (dsu.sameSet(u[i], v[i]) == 0) {
            needed[i] = 1;
            dsu.uni(u[i], v[i]);
            adj.addBiEdge(u[i], v[i], w[i]);
        }
    }
    for (int i = 0; i < n - 1; i++) {
        ok[i] = 1;
    }
    vector<pair<int, int> > ans;
    for (int i = n - 1; i < m; i++) {
        if (!needed[i]) continue;
        int a = u[i];
        int b = v[i];
        target = b;
        r = 0;

        for (int j = 0; j < m; j++) {
            if (ok[j]) {
                dsu.uni(u[j], v[j]);
                if (dsu.sameSet(a, b)) {
                    ok[j] = 0;
                    ok[i] = 1;
                    ans.pb({j, i});
                    break;
                }
            }
        }
    }
    cout << ans.size() << endl;
    for (auto &u : ans) {
        cout << u.fi + 1 << " " << u.se + 1 << endl;
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    while (T--) {
        test_case();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 17928kb

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: 18036kb

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:

2
1 7
2 8

result:

wrong answer not a spanning tree after swap 2