QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#354631#6560. Broken Minimum Spanning TreeDelay_for_five_minutes#WA 1ms3668kbC++202.2kb2024-03-15 19:32:402024-03-15 19:32:41

Judging History

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

  • [2024-03-15 19:32:41]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3668kb
  • [2024-03-15 19:32:40]
  • 提交

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