QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#134468#6560. Broken Minimum Spanning TreeNoobie_99#WA 1ms3520kbC++201.6kb2023-08-03 20:28:262023-08-03 20:28:28

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-03 20:28:28]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3520kb
  • [2023-08-03 20:28:26]
  • 提交

answer

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

#define tsolve int t; cin >> t; while(t--) solve
#define debug(x) cerr << __LINE__ << ": "#x" = " << (x) << endl
#define nl '\n'
#define all(x) ::begin(x), ::end(x)
#define sz(x) (int)::size(x)
using ll = long long;
using ld = long double;

struct edge {
	ll from, to, weight, id;
};

ll n, m;
vector<vector<edge>> adj;  
vector<edge> edges;
vector<bool> in_tree;

pair<ll, ll> max_weight(ll c, ll f, ll t, ll id = -1, ll w = 0) {
	if (c == t) {
		return { w, id };
	}

	for (edge e : adj[c]) {
		if (e.to == f) continue;
		if (!in_tree[e.id]) continue;

		auto [rw, rid] = max_weight(e.to, c, t, e.id, e.weight);
		if (rw == 0) continue;

		if (w > rw) return { w, id };
		else return { rw, rid };
	}

	return { 0, -1 };
}

void solve() {
    cin >> n >> m;
	adj.resize(n);
	in_tree.resize(n);
	for (ll i = 0; i < m; ++i) {
		ll u, v, w;
		cin >> u >> v >> w;
		--u; --v;

		adj[u].push_back({ u, v, w, i });
		adj[v].push_back({ v, u, w, i });
		edges.push_back({ u, v, w, i });
		in_tree[i] = i < n - 1;
	}

	sort(all(edges), [](edge x, edge y) {
		return x.weight < y.weight;
	});

	vector<pair<ll, ll>> res;
	for (edge e : edges) {
		if (in_tree[e.id]) continue;
		auto [rw, rid] = max_weight(e.from, e.from, e.to);

		if (rw < e.weight) continue;
		in_tree[rid] = false;
		in_tree[e.id] = true;
		res.push_back({ rid, e.id });
	}

	cout << ssize(res) << nl;
	for (auto [u, v] : res) {
		cout << (u + 1) << ' ' << (v + 1) << nl;
	}
}
 
int main() {
	cin.tie(0)->sync_with_stdio(false);
	cout << setprecision(16);
	solve();
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3476kb

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

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:

5
2 7
5 8
1 2
4 5
3 6

result:

FAIL participant's plan is better than jury!