我是题面



fammer john 限时回归
下面是题解:
根据题意,场是点,道路是边,他要删掉边,不就是最小生成树?
Kruskal秒了(bushi)
直接搬模板你只会得到一个大大的WAAAAAAA
prim肯定是不可以的,会爆
john还需要安慰奶牛
你首先要决定那些道路是需要保留的N-1条道路。第j条双向道路连接了牧场Sj和Ej,而且走完它需要Lj的时间。没有两个牧场是被一条以上的道路所连接(找最小生成树)。
每次你到达第i个牧场的时候(即使你已经到过),你必须花去Ci的时间和奶牛交谈走之前找好的最小生成树的路,每个点可能会经过多次,每经过一次就谈一次话ci,可以自己脑补一下,就像dfs回溯遍历每一条路,直到走完。
说明这道题需要同时处理点权和边权, ![]()
那该怎么办?
![]()
首先,这条路要被来回走两遍(因为是树),所以在总权值里要有它× 2 \times2×2
其次,每头奶牛会被安慰两次,这样可以想到要加入2倍的点权,但是再更新下一条时就又会被重复计算,所以只需要算一次就行。
这样中间节点都是两次,两端是1次,但是题目的特殊要求要起点算2次,所以先在读入点权时就找到最小的数最后加入即可
我是部分代码
for(int i=1; i<=m; i++) {
int xx=find();
int yy=find();
if(xx!=yy) {
fa[xx]=yy;
sum+=a[i].v;
[a[i].x]++;
[a[i].y]++;
}
}
我的代码里做了个处理
过不了可以尝试加一下
for(int i=1;i<=; i++) {
cin>>a[i].x>>a[i].y>>a[i].v;
a[i].v=2*a[i].v+c[a[i].x]+c[a[i].y];
}
并查集find查找一下属不属于同一个集合内,递归下去寻找并查集不会来学最小生成树的是这个 ![]()
最后打一个小擂台
int minn=0x3f3f3f3f;
for(int i=1; i<=n; i++){
if(minn>c[i]){
minn=c[i];
}
}
sum+=minn;
秒了
蒟蒻第一次写题解,有问题欢迎大蛇指出 ![]()
fammer John 是个人物 ![]()