QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#128255 | #6560. Broken Minimum Spanning Tree | installb# | WA | 1ms | 3700kb | C++14 | 2.2kb | 2023-07-20 19:36:34 | 2023-07-20 19:36:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 8005;
int fa[N],dep[N],fw[N];
int eu[N],ev[N],w[N];
int swp[N];
vector <pair <int,int> > G[N];
void dfs(int u,int f){
fa[u] = f;
dep[u] = dep[f] + 1;
for(auto [v,ew] : G[u]){
if(v == f) continue;
dfs(v,u);
fw[v] = ew;
}
}
pair <int,int> get_max(int u,int v){
vector <pair <int,int> > H;
if(dep[u] < dep[v]) swap(u,v);
while(dep[u] < dep[v]){
H.push_back({w[fw[u]],-fw[u]});
u = fa[u];
}
while(u != v){
H.push_back({w[fw[u]],-fw[u]});
H.push_back({w[fw[v]],-fw[v]});
u = fa[u]; v = fa[v];
}
sort(H.begin(),H.end());
return H.back();
}
void solve(){
int n,m;
cin >> n >> m;
for(int u,v,i = 1;i < n;i ++){
cin >> u >> v >> w[i];
eu[i] = u; ev[i] = v;
G[u].push_back({v,i});
G[v].push_back({u,i});
}
for(int i = n;i <= m;i ++){
int u,v;
cin >> u >> v >> w[i];
eu[i] = u; ev[i] = v;
dfs(1,0);
auto [ew,id] = get_max(u,v);
// cout << ew << ' ' << id << endl;
id = -id;
if(ew > w[i]){
int las = id;
if(las >= n) las = swp[las];
swp[las] = i;
swp[i] = las;
for(int j = 0;j < G[eu[id]].size();j ++){
if(G[eu[id]][j].first == ev[id]){
swap(G[eu[id]][j],G[eu[id]].back());
}
}
for(int j = 0;j < G[ev[id]].size();j ++){
if(G[ev[id]][j].first == eu[id]){
swap(G[ev[id]][j],G[ev[id]].back());
}
}
G[eu[id]].pop_back();
G[ev[id]].pop_back();
G[u].push_back({v,i});
G[v].push_back({u,i});
}
}
vector <pair <int,int> > ans;
for(int i = 1;i < n;i ++){
if(swp[i]) ans.push_back({i,swp[i]});
}
cout << ans.size() << '\n';
for(auto [u,v] : ans) cout << u << ' ' << v << '\n';
}
signed main(){
ios::sync_with_stdio(false);
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3656kb
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: 1ms
memory: 3700kb
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 3 8
result:
wrong answer not a spanning tree after swap 2