QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#152699#6560. Broken Minimum Spanning TreeBUET_POISSON#RE 0ms3856kbC++203.0kb2023-08-28 17:52:262023-08-28 17:52:26

Judging History

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

  • [2023-08-28 17:52:26]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3856kb
  • [2023-08-28 17:52:26]
  • 提交

answer

#include <bits/stdc++.h>
 
using namespace std;
#define getbit(n, i) (((n) & (1LL << (i))) != 0) 
#define setbit0(n, i) ((n) & (~(1LL << (i)))) 
#define setbit1(n, i) ((n) | (1LL << (i))) 
#define togglebit(n, i) ((n) ^ (1LL << (i))) 
#define lastone(n) ((n) & (-(n))) 
char gap = 32;
#define int long long
#define ii pair<int, int>

#define ll long long 
#define lll __int128_t
#define pb push_back

vector<pair<int, int>> adj[2001];

int parent[2001];
int parent_wt[2001];
void recalc(int root, int par, int wt) {
    parent[root] = par;
    parent_wt[root] = wt;
    for(auto x: adj[root]) {
        if(x.first == par) continue;
        recalc(x.first, root, x.second);
    }
}

void add_edge(int x, int y, int w) {
    adj[x].push_back({y, w});
    adj[y].push_back({x, w});
}

void remove_edge(int x, int y, int w) {
    vector<pair<int, int>> temp;
    for(auto xx: adj[x]) {
        if(xx.first == y and xx.second == w) continue;
        temp.push_back(xx);
    }
    adj[x].clear();
    adj[x] = temp;

    temp.clear();
    for(auto yy: adj[y]) {
        if(yy.first == x and yy.second == w) continue;
        temp.push_back(yy);
    }

    adj[y].clear();
    adj[y] = temp;
    temp.clear();

}

vector<pair<int, int>> extra_edge;
map<pair<pair<int, int>, int>, int> id;

int find_black_sheep(int x, int y, int w) {
    recalc(x, 0, 0);
    int curr = y;
    int max_val = 0;
    int max_id = -1;
    while(curr != x) {
        int idx = id[{{curr, parent[curr]}, parent_wt[curr]}];
        if(max_val < parent_wt[curr]) max_val = parent_wt[curr], max_id = idx;
        curr = parent[curr];
    }
    if(max_val <= w) return -1;

    return max_id;
}



void solve() {
    int n, m; cin >> n >> m;
    vector<pair<pair<int, int>, int>> edges;
    
    for(int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        if(i <= n - 1) {
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }
        edges.push_back({{u, v}, w});
        id[{{u, v}, w}] = i - 1;
    }

    for(int i = n - 1; i < m; i++) {
        extra_edge.push_back({edges[i].second, i});
    }

    sort(extra_edge.begin(), extra_edge.end());

    int ans = 0;
    vector<pair<int, int>> res;


    for(int i = 0; i < extra_edge.size(); i++) {
        int idx = extra_edge[i].second;
        idx = find_black_sheep(edges[idx].first.first, edges[idx].first.second, edges[idx].second);
        if(idx == -1) {
            continue;
        }
        int rem = idx + 1;
        ans++;
        remove_edge(edges[idx].first.first, edges[idx].first.second, edges[idx].second);
        idx = extra_edge[i].second;
        int ad = idx + 1;
        res.push_back({rem, ad});
        add_edge(edges[idx].first.first, edges[idx].first.second, edges[idx].second);
    }

    cout << ans << "\n";
    for(auto x: res) cout << x.first << " " << x.second << "\n";
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    solve();
    
}

详细

Test #1:

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

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
Runtime Error

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: