QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#277139#6560. Broken Minimum Spanning Treeucup-team1198#RE 1ms3848kbC++142.1kb2023-12-06 15:38:452023-12-06 15:38:46

Judging History

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

  • [2023-12-06 15:38:46]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3848kb
  • [2023-12-06 15:38:45]
  • 提交

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

output:


result: