QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#152712 | #6560. Broken Minimum Spanning Tree | BUET_POISSON# | RE | 1ms | 3612kb | C++20 | 2.7kb | 2023-08-28 18:16:58 | 2023-08-28 18:16:59 |
Judging History
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
set<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].insert({y, w});
adj[y].insert({x, w});
}
void remove_edge(int x, int y, int w) {
adj[x].erase({y, w});
adj[y].erase({x, w});
}
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) {
add_edge(u, v, 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});
}
if(extra_edge.size() >= 2)
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: 1ms
memory: 3612kb
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