QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#354822#6560. Broken Minimum Spanning Treekevinshan#WA 1ms3644kbC++171.8kb2024-03-16 03:32:022024-03-16 03:32:02

Judging History

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

  • [2024-03-16 03:32:02]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3644kb
  • [2024-03-16 03:32:02]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define f first
#define s second

const int MAXN = 2005;
vector<pair<int, int>> adj[MAXN];

struct ed  {
    int u, v, w, i;
    friend bool operator<(ed a, ed b) {
        return a.w < b.w;
    }
    friend bool operator==(ed a, ed b){
        return a.u == b.u && a.v == b.v;
    }
};
struct DSU {
    vector<int> d;
    void init(int N) { d = vector<int>(N, -1); }
    int get(int x) { return d[x] < 0 ? x: d[x] = get(d[x]); }
    bool same(int a, int b) { return get(a) == get(b); }
    bool unite(int x, int y) {
        x = get(x); y = get(y); if(x == y) return 0;
        if (d[x] > d[y]) swap(x, y);
        d[x] += d[y]; d[y] = x; return 1;
    }
};


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (fopen("input.in", "r")) {
        freopen("input.in", "r", stdin);
        freopen("output.out", "w", stdout);
    }
    int n, m;
    cin>>n>>m;
    vector<ed> orig;
    vector<ed> eds;
    for(int i=0; i<m; i++){
        int u,v,w;
        cin>>u>>v>>w;
        if(u > v) swap(u, v);
        adj[--u].pb({--v, w});
        adj[v].pb({u,w});
        if(i<n-1) orig.pb({u,v,w,i});
        else eds.pb({u,v,w,i});
    }
    sort(all(eds));
    vector<pair<int, int>> ans;
    for(auto e : orig) {
        DSU d; d.init(n);
        int u = e.u;
        int v = e.v;
        // cout<<u<<" "<<v<<"\n";
        for(auto ee:orig) {
            if(!(e == ee)) d.unite(e.u,e.v);
        }
        for(auto ee:eds){
            if(ee.w >= e.w) break;
            if(d.get(ee.u) != d.get(ee.v)) {
                ans.pb({e.i, ee.i});
            }
        }
    }
    cout<<ans.size()<<"\n";
    for(auto p:ans) cout<<p.f+1<<" "<<p.s+1<<"\n";
    


}


詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3644kb

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: 3584kb

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:

10
1 7
1 8
2 7
2 8
3 7
3 8
4 7
4 8
5 7
5 8

result:

wrong answer Integer parameter [name=k] equals to 10, violates the range [0, 8]