QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#240829#6560. Broken Minimum Spanning TreeMovingUp#Compile Error//C++143.0kb2023-11-05 20:02:132023-11-05 20:02:13

Judging History

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

  • [2023-11-05 20:02:13]
  • 评测
  • [2023-11-05 20:02:13]
  • 提交

answer

#include <iostream>
#include <vector>

using namespace std;

struct edge {
  int id;
  int u, v, w;

  bool operator<(const edge &o) const { return w < o.w; }
};

struct dsu {
  vector<int> parent, subtree;

  void init(int n) {
    parent.resize(n);
    subtree.resize(n);

    for (int i = 0; i < n; i++) {
      subtree[i] = 1;
      parent[i] = i;
    }
  }

  int findParent(int x) {
    if (parent[x] == x)
      return x;
    else {
      parent[x] = findParent(parent[x]);
      return parent[x];
    }
  }

  void unite(int parX, int parY) {
    if (subtree[parX] < subtree[parY]) {
      parent[parX] = parY;
      subtree[parY] += subtree[parX];
    } else {
      parent[parY] = parX;
      subtree[parX] += subtree[parY];
    }
  }
};

int64_t findMst(int n, const vector<edge> &edges, int edgeId) {
  dsu d;
  d.init(n);

  int64_t ans = 0;
  for (auto e : edges) {
    if (e.id == edgeId) {
      ans += e.w;
      d.unite(e.u, e.v);
    }
  }

  for (auto e : edges) {
    if (e.id == edgeId) {
      continue;
    }

    int parX = d.findParent(e.u);
    int parY = d.findParent(e.v);

    if (parX != parY) {
      ans += e.w;
      d.unite(parX, parY);
    }
  }

  return ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;

  vector<edge> edges(m);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;

    u--;
    v--;

    edges[i] = {i, u, v, w};
  }

  sort(edges.begin(), edges.end());

  int64_t globalMst = findMst(n, edges, -1);

  vector<bool> keep(n - 1, false);
  for (int i = 0; i < n - 1; i++) {
    int64_t currMst = findMst(n, edges, i);

    if (currMst == globalMst) {
      keep[i] = true;
    }
  }

  dsu d;
  d.init(n);

  vector<edge> oldEdges;
  for (auto e : edges) {
    if (e.id >= n - 1)
      continue;

    if (keep[e.id]) {
      int parX = d.findParent(e.u);
      int parY = d.findParent(e.v);

      d.unite(parX, parY);
    } else {
      oldEdges.push_back(e);
    }
  }

  vector<edge> newEdges;
  for (auto e : edges) {
    if (e.id < n - 1)
      continue;

    int parX = d.findParent(e.u);
    int parY = d.findParent(e.v);

    if (parX != parY) {
      d.unite(parX, parY);
      newEdges.push_back(e);
    }
  }

  d.init(n);
  for (auto e : edges) {
    if (e.id < n - 1 && keep[e.id]) {
      int parX = d.findParent(e.u);
      int parY = d.findParent(e.v);

      d.unite(parX, parY);
    }
  }

  vector<bool> taken(m, false);
  vector<pair<int, int>> changes;
  for (auto oe : oldEdges) {
    for (auto ne : newEdges) {
      if (taken[ne.id])
        continue;

      int parX1 = d.findParent(oe.v);
      int parY1 = d.findParent(oe.u);

      int parX2 = d.findParent(ne.v);
      int parY2 = d.findParent(ne.u);

      if ((parX1 == parX2 && parY1 == parY2) ||
          (parX1 == parY2 && parY1 == parX2)) {
        taken[ne.id] = true;
        changes.push_back({oe.id, ne.id});

        d.unite(parX1, parY1);
        break;
      }
    }
  }

  cout << changes.size() << endl;
  for (auto [x, y] : changes) {
    cout << x + 1 << " " << y + 1 << endl;
  }
}

详细

answer.code: In function ‘int main()’:
answer.code:93:3: error: ‘sort’ was not declared in this scope; did you mean ‘short’?
   93 |   sort(edges.begin(), edges.end());
      |   ^~~~
      |   short
answer.code:173:13: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’
  173 |   for (auto [x, y] : changes) {
      |             ^