题解 P1340 【兽径管理】

题解 P1340 【兽径管理】

蒟蒻在线暴力过了！！！

提供一个灰常暴力的在线做法

就像其他dalao所说，这题就是一个克鲁斯卡尔。

但似乎不用离线，直接在线暴力加边，暴力处理就好了，每次对于读入的边，

因为这条边的价值可能对当前答案产生影响，所以把这条边入队，就是每次重新跑一边快排，然后在重新跑一边克鲁斯卡尔，时间O(n lg n*w)

重新并查集找一次最短路，还有一种方法是因为已经排好了前面的序列，所以插当前边的时候用插入排序即可(没试过)

最后只要当前的答案不为-1，那么下面所有的答案也肯定小于等于当前答案，因为

肯定能用这次的几条边组成答案。

只不过需要卡卡常(逃

代码：

// luogu-judger-enable-o2//洛谷自带的O2
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")//24行大优化(卡常)
p.s 正式比赛最好不用这种方法，否则可能会出现莫名的CE啦
#include<bits/stdc++.h>
using namespace std;
struct E {
int x,y,z;
} a[500005];//结构体存图排序更方便
int n,m,t;
int fa[500005],b[500005],c[500005];

inline int read(){
register int x=0;register char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);ch=getchar())x=x*10+(ch&15);
return x;
}//快读(卡常)输出就n个数，所以不用打快输
bool cmp(E x,E y) {
return x.z < y.z;//按价值从小到大排
}//克鲁斯卡尔按路的长度排序
int find(int x) {
if (fa[x] != x) fa[x] = find(fa[x]);//路径压缩，并查集常用技巧
return fa[x];
}//并查集找祖宗
int main() {
n=read();
m=read();
for (int i=1; i<=m; ++i) {
a[i].x=read();
a[i].y=read();
a[i].z=read();//读入
t++;//t代表当前有几个数(其实相当于i,也可以删了)
sort(a + 1,a + t + 1,cmp);//每读一次重新快排一遍
for (int i=1; i<=n; ++i) fa[i]=i;//每次初始化
int k=0, ans=0;
for (int j=1; j<=t; ++j)//对当前的t个数做克鲁斯卡尔
if (find(a[j].x)!=find(a[j].y)) {
fa[find(a[j].x)]=find(a[j].y);//连根
ans+=a[j].z;//找到了答案加上价值
k++;//k代表当前已选择的边条数，
}//并查集找+合并，其中k代表有几个点能走到
if (k==n-1) {//如果所有城市之间都有边联通
printf("%d\n",ans);
continue;
}
cout<<-1<<endl;//还有点走不到，输-1
}
}