QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#277139 | #6560. Broken Minimum Spanning Tree | ucup-team1198# | RE | 1ms | 3848kb | C++14 | 2.1kb | 2023-12-06 15:38:45 | 2023-12-06 15:38:46 |
Judging History
answer
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
const int MAXN = 1e4;
vector<array<int, 2>> g[MAXN];
int wgh[MAXN];
int ind = -1;
bool dfs(int v, int goal, int p = -1) {
if (v == goal) {
return true;
}
for (auto e : g[v]) {
if (e[0] == p) continue;
int mem = ind;
int i = e[1];
if (ind == -1) {
ind = i;
} else if (wgh[i] > wgh[ind]) {
ind = i;
} else if (wgh[i] == wgh[ind] && i > ind) {
ind = i;
}
if (dfs(e[0], goal, v)) {
return true;
}
ind = mem;
}
return false;
}
int main() {
#ifdef DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#endif
int n, m;
cin >> n >> m;
vector<array<int, 4>> ed(m);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
--u; --v;
wgh[i] = w;
ed[i] = {w, i, u, v};
if (i < n - 1) {
g[u].push_back({v, i});
g[v].push_back({u, i});
}
}
sort(ed.begin(), ed.end());
vector<array<int, 2>> ans;
for (auto elem : ed) {
ind = -1;
dfs(elem[2], elem[3]);
int i = elem[1];
bool change = false;
if (wgh[i] < wgh[ind]) {
change = true;
} else if (wgh[i] == wgh[ind] && i < ind) {
change = true;
}
if (!change) continue;
ans.push_back({ind, i});
for (int v = 0; v < n; ++v) {
vector<array<int, 2>> g1;
for (auto e : g[i]) {
if (e[1] != ind) {
g1.push_back(e);
}
}
g[i] = move(g1);
}
g[elem[2]].push_back({elem[3], i});
g[elem[3]].push_back({elem[2], i});
}
cout << ans.size() << "\n";
for (auto elem : ans) {
cout << elem[0] + 1 << " " << elem[1] + 1 << "\n";
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3848kb
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
Runtime Error
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