题目大意
最开始没有道路，每周会出现一条新的道路，求每一周出现新的道路后的最小生成树
思路
首先想到的是每次读入一条路径都去做一遍$Kruskal$，但是肯定会$T$成狗
翻了翻题解看到了$dalao$的做法
将$W$条边全部读入后
先对$W$条边做一遍$Kruskal$，然后从后往前倒着判断，这一周加的边是否在当前的MST中出现过
如果出现过，那就说明要重新做一遍$Kruskal$，知道无法找到$MST$，就可以$Break$了，既然现在找不到，那之前肯定也找不到
$%%% dalao %%%$
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, f[
20800], Ans[
600700], tot;
bool book[
600700], vis[
600700];
struct edge {
int u, v, w;
int num;
}ed[600700];
int find(
int x) {
if(x == f[x])
return x;
else return f[x] =
find(f[x]);
}
inline bool Kruskal(
int s) {
memset(book, 0,
sizeof(
0));
tot =
0;
for(
int i=
1; i<=n; i++) f[i] =
i;
for(
int i=
1; i<=m; i++
) {
int xx = find(ed[i].u), yy =
find(ed[i].v);
if(xx != yy && !
vis[ed[i].num]) {
book[ed[i].num] =
1;
f[xx] =
find(yy);
Ans[s] +=
ed[i].w;
tot++
;
}
if(tot == n-
1) {
return true;
break;
}
}
Ans[s] = -
1;
return false;
}
inline bool cmp(edge a, edge b) {
return a.w <
b.w;
}
int main() {
scanf("%d%d", &n, &
m);
for(
int i=
1; i<=m; i++
) {
scanf("%d%d%d", &ed[i].u, &ed[i].v, &
ed[i].w);
ed[i].num =
i;
}
sort(ed+
1, ed+
1+
m, cmp);
bool mark;
Kruskal(m);
vis[m] =
1;
for(
int i=m-
1; i>=
1; i--
) {
vis[i+
1] =
1;
if(book[i+
1] ==
1) {
mark =
Kruskal(i);
if(!
mark) {
for(
int j=
1; j<i; j++) Ans[j] = -
1;
for(
int j=
1; j<=m; j++
) {
printf("%d\n", Ans[j]);
}
return 0;
}
}
else Ans[i] = Ans[i+
1];
}
for(
int j=
1; j<=m; j++
) {
printf("%d\n", Ans[j]);
}
return 0;
}
转载于:https://www.cnblogs.com/bljfy/p/9292913.html
相关资源：锣鼓声声迎新春——新年工作计划ppt模板.zip
