社区讨论
萌新刚学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 条回复,欢迎继续交流。
正在加载回复...