QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#354822 | #6560. Broken Minimum Spanning Tree | kevinshan# | WA | 1ms | 3644kb | C++17 | 1.8kb | 2024-03-16 03:32:02 | 2024-03-16 03:32:02 |
Judging History
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]