QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#349203 | #6560. Broken Minimum Spanning Tree | realcomplex0# | WA | 1ms | 3856kb | C++20 | 3.2kb | 2024-03-10 00:01:09 | 2024-03-10 00:01:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
struct edge{
int uu;
int vv;
int ww;
int id;
bool operator< (const edge &ee) const {
return ww < ee.ww;
}
};
const int N = 2050;
int par[N];
int fin(int u){
if(par[u] == u) return u;
return par[u]=fin(par[u]);
}
bool unite(int u, int v){
u=fin(u);
v=fin(v);
if(u==v)return false;
par[u]=v;
return true;
}
int n;
void init(){
for(int i = 1; i <= n; i ++ ) par[i] = i;
}
const int M = 3010;
int A[M], B[M];
vector<int> T[N];
int dep[N];
vector<int> ao;
vector<int> bo;
pii up[N];
void dfs(int u, int par){
for(auto x : T[u]){
if(x == par) continue;
dep[x]=dep[u]+1;
dfs(x, u);
}
}
bool del[N];
int fa = -1, fb = -1;
void fin(int u, int pa){
for(auto x : T[u]){
if(x == pa) continue;
fin(x, u);
up[u]=min(up[u],up[x]);
}
if(del[u] != -1 && up[u].fi < dep[u]){
fa = del[u];
fb = up[u].se;
}
}
void flip(){
for(int i = 1; i <= n; i ++) {
T[i].clear();
up[i] = mp((int)1e9, -1);
del[i] = -1;
}
for(int i = 1; i <= n - 1; i ++ ){
T[A[i]].push_back(B[i]);
T[B[i]].push_back(A[i]);
}
dfs(1,1);
for(auto x : bo){
if(x == -1) continue;
if(dep[A[x]] < dep[B[x]]) swap(A[x], B[x]); // A[x] is deep
up[A[x]]=min(up[A[x]], mp(dep[B[x]], x));
}
for(auto x : ao){
if(x == -1) continue;
if(dep[A[x]] < dep[B[x]]) swap(A[x], B[x]);
del[A[x]] = x;
}
fa = -1;
fb = -1;
fin(1, -1);
for(auto &x : ao){
if(x == fa) x = -1;
}
for(auto &x : bo){
if(x == fb) x = -1;
}
swap(A[fa], A[fb]);
swap(B[fa], B[fb]);
cout << fa << " " << fb << "\n";
}
int main(){
fastIO;
//freopen("in.txt", "r", stdin);
int m;
cin >> n >> m;
int u, v, w;
vector<edge> ee;
for(int i = 1; i <= m; i ++) {
cin >> u >> v >> w;
ee.push_back({u, v, w, i});
A[i] = u;
B[i] = v;
}
sort(ee.begin(), ee.end());
int good = 0;
vector<edge> cum;
for(int i = 0 ; i < ee.size(); i ++ ){
cum.push_back(ee[i]);
if(i + 1 == ee.size() || ee[i].ww != ee[i + 1].ww){
init();
for(int j = 0 ; j < i ; j ++ ){
if(ee[j].ww < ee[i].ww){
unite(ee[j].uu, ee[j].vv);
}
}
for(auto f : cum){
if(f.id <= n - 1 && !unite(f.uu, f.vv)){
ao.push_back(f.id);
}
}
for(auto f : cum){
if(f.id >= n && unite(f.uu, f.vv)){
bo.push_back(f.id);
}
}
cum.clear();
}
}
int sz = ao.size();
cout << sz << "\n";
for(int i = 0; i < sz; i ++ ) flip();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3800kb
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: 3856kb
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 1 8
result:
wrong answer bad swap 1 8