社区讨论

萌新刚学OI,输出-1求调

P1340[IOI 2003] 兽径管理参与者 7已保存回复 15

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
15 条
当前快照
1 份
快照标识符
@mhj23usq
此快照首次捕获于
2025/11/03 19:28
4 个月前
此快照最后确认于
2025/11/03 20:37
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 205, MAXW = 6005;
int n, m, w;
int hd[MAXW], fa[MAXN], vis[2 * MAXW], da[2 * MAXW], ret[MAXW];
struct node{
	int from, to, dt, nxt, id;
	bool operator<(const node &other)const{
		return dt < other.dt;
	}
}e[2 * MAXW];
void add(int u, int v, int w){
	e[++ m].from = u;
	e[m].to = v;
	e[m].dt = w;
	e[m].nxt = hd[u];
	hd[u] = m;
}
int find(int x){
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int Kruskal(){
	memset(vis, 0, sizeof vis);
	for(int i = 1; i <= n; ++ i)
		fa[i] = i;
	int ce = 0, ans = 0;
	for(int i = 1; i <= m; ++ i){
		if(da[e[i].id])
			continue;
		int f1 = find(e[i].from), f2 = find(e[i].to);
		if(f1 != f2){
			ans += e[i].dt;
			++ ce;
			vis[e[i].id] = 1;
			fa[f1] = f2;
		}
		if(ce == n - 1)
			break;
	}
	return ce == n - 1 ? ans : -1;
}
signed main(){
	cin >> n >> w;
	for(int i = 1, u, v, w; i <= w; ++ i)
		cin >> u >> v >> w, add(u, v, w), e[i].id = i;
	sort(e + 1, e + m + 1);
	ret[w] = Kruskal();
	for(int i = w - 1; i; -- i){
		da[i + 1] = 1;
		if(vis[i + 1])
			ret[i] = Kruskal();
		else
			ret[i] = ret[i + 1];
		if(ret[i] == -1){
			for(int j = 1; j < i; ++ j)
				ret[j] = -1;
			break;
		}
	}
	for(int i = 1; i <= w; ++ i)
		cout << ret[i] << "\n";
}

回复

15 条回复,欢迎继续交流。

正在加载回复...