QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#349203#6560. Broken Minimum Spanning Treerealcomplex0#WA 1ms3856kbC++203.2kb2024-03-10 00:01:092024-03-10 00:01:09

Judging History

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

  • [2024-03-10 00:01:09]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3856kb
  • [2024-03-10 00:01:09]
  • 提交

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