QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#354631 | #6560. Broken Minimum Spanning Tree | Delay_for_five_minutes# | WA | 1ms | 3668kb | C++20 | 2.2kb | 2024-03-15 19:32:40 | 2024-03-15 19:32:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n , m;
struct ed {
int u , v , w;
int id;
};
vector<ed> Ed , tree , re , ini , nw;
struct dst {
int f[2005];
void cls() {
for(int i = 1;i <= n;i++) f[i] = i;
}
int Find(int x) {
return f[x] == x ? f[x] : f[x] = Find(f[x]) ;
}
void Merge(int x,int y) {
int a = Find(x) , b = Find(y);
f[a] = b;
}
}d;
map<int,int> mp;
int main() {
ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
cin >> n >> m;
for(int i = 1;i <= m;i++) {
int u , v , w;
cin >> u >> v >> w;
Ed.push_back((ed){u , v, w , i});
if(i <= n - 1) tree.push_back(Ed.back()) ;
}
sort(Ed.begin() , Ed.end() , [&](ed x,ed y){return x.w < y.w ;}) ;
d.cls() ;
for(int i = 0 ; i < Ed.size() ;i++) {
int u = Ed[i].u , v= Ed[i].v ;
int a = d.Find(u) , b = d.Find(v) ;
if(a == b) continue ;
d.f[a] = b;
mp[Ed[i].w]++ ;
}
for(int i = 0;i < tree.size();i++) {
if(mp[tree[i].w]) {
mp[tree[i].w]--;
ini.push_back(tree[i]) ;
}
else {
re.push_back(tree[i]) ;
}
}
d.cls() ;
for(int i = 0;i < ini.size();i++) {
d.Merge(ini[i].u , ini[i].v) ;
}
for(int i = 0;i < Ed.size();i++) {
int a = d.Find(Ed[i].u) , b = d.Find(Ed[i].v) ;
if(a == b) continue ;
d.f[a] = b;
nw.push_back(Ed[i]) ;
}
cout << re.size() << '\n' ;
for(int i = re.size() - 1;i >= 0;i--) {
d.cls() ;
for(int j = 0;j < ini.size();j++) d.Merge(ini[j].u , ini[j].v) ;
for(int j = 0;j < i;j++) {
d.Merge(re[j].u , re[j].v) ;
}
bool ff = 0;
for(int j = 0;j < nw.size();j++) {
int a = d.Find(nw[j].u ) , b = d.Find(nw[j].v) ;
if(a != b) {
ff = 1;
cout << re[i].id <<' ' << nw[j].id << '\n' ;
ini.push_back(nw[j]) ;
nw.erase(nw.begin() + j);
break ;
}
}
assert(ff) ;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3668kb
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: 3656kb
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 5 8 4 4
result:
wrong answer bad swap 4 4