首页 技术 正文
技术 2022年11月23日
0 收藏 967 点赞 4,441 浏览 7914 个字

  这题在浴谷夏令营wyx在讲的最小生成树的时候提到过,但并没有细讲怎么写…

  这题可以用三种写法写,虽然只有两种能过。。。(倍增/倍增+并查集/树链剖分

  先跑出最小生成树,分类讨论,在MST上的边,考虑用可以对这条边有影响的(判断是否有影响同后面)不在MST上的边的最小值-1来更新,不在MST上的边u->v,考虑用MST上u到v的路径上的边的最大值-1来更新。

  显然用倍增就可以了,细节看代码。复杂度O(NlogN)

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#define ll long long
using namespace std;
const int maxn=,inf=2e9;
struct poi{int x,y,z,pos;}a[maxn];
struct zs{int too,dis,pre;}e[maxn];
int n,m,x,y,z,tot;
int last[maxn],ans[maxn],mn[maxn][],mx[maxn][],f[maxn][],fa[maxn],d[maxn];
bool ty[maxn];
void read(int &k)
{
int f=;k=;char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(c<=''&&c>='')k=k*+c-'',c=getchar();
k*=f;
}
bool cmp(poi a,poi b){return a.z<b.z;}
void add(int x,int y,int z){e[++tot].too=y;e[tot].dis=z;e[tot].pre=last[x];last[x]=tot;}
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
void dfs(int x,int fa)
{
f[x][]=fa;d[x]=d[fa]+;
for(int i=last[x];i;i=e[i].pre)
if(e[i].too!=fa)
{
mx[e[i].too][]=e[i].dis;
dfs(e[i].too,x);
}
}
inline int query(int x,int y)
{
int ans=;
if(d[x]<d[y])swap(x,y);
for(int i=;i>=;i--)
if(d[f[x][i]]>=d[y])ans=max(ans,mx[x][i]),x=f[x][i];
if(x==y)return ans;
for(int i=;i>=;i--)
if(f[x][i]!=f[y][i])ans=max(ans,max(mx[x][i],mx[y][i])),x=f[x][i],y=f[y][i];
return max(ans,max(mx[x][],mx[y][]));
}
void update(int x,int y,int delta)
{
if(d[x]<d[y])swap(x,y);
for(int i=;i>=;i--)
if(d[f[x][i]]>=d[y])mn[x][i]=min(mn[x][i],delta),x=f[x][i];
if(x==y)return;
for(int i=;i>=;i--)
if(f[x][i]!=f[y][i])mn[x][i]=min(mn[x][i],delta),mn[y][i]=min(mn[y][i],delta),x=f[x][i],y=f[y][i];
mn[x][]=min(mn[x][],delta);mn[y][]=min(mn[y][],delta);
}
int main()
{
read(n);read(m);
for(int i=;i<=m;i++)read(a[i].x),read(a[i].y),read(a[i].z),a[i].pos=i;
for(int i=;i<=n;i++)fa[i]=i;
sort(a+,a++m,cmp);
for(int i=;i<=m;i++)
{
int fx=gf(a[i].x),fy=gf(a[i].y);
if(fx==fy)continue;
add(a[i].x,a[i].y,a[i].z);
add(a[i].y,a[i].x,a[i].z);
fa[fx]=fy;ty[i]=;
}
dfs(,);
for(int j=;j<;j++)for(int i=;i<=n;i++)mx[i][j]=max(mx[i][j-],mx[f[i][j-]][j-]),f[i][j]=f[f[i][j-]][j-];
memset(mn,0x7f,sizeof(mn));
for(int i=;i<=m;i++)
if(!ty[i])
{
ans[a[i].pos]=query(a[i].x,a[i].y)-;
update(a[i].x,a[i].y,a[i].z);
}
for(int j=;j>=;j--)for(int i=;i<=n;i++)mn[i][j-]=min(mn[i][j-],mn[i][j]),mn[f[i][j-]][j-]=min(mn[f[i][j-]][j-],mn[i][j]);
for(int i=;i<=m;i++)if(ty[i])ans[a[i].pos]=(d[a[i].x]>d[a[i].y]?mn[a[i].x][]:mn[a[i].y][])-;
for(int i=;i<=m;i++)printf("%d ",ans[i]>=inf?-:ans[i]);
return ;
}

  显然还可以写链剖。。但是两个log就TLE了。。。 MDZZ原来是我写残了,可以过的

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#define ll long long
using namespace std;
const int maxn=,inf=2e9;
struct zs{int too,pre,dis;}e[maxn*];
struct tjm{int max,min,delta;}tree[maxn*];
struct poi{int x,y,z,pos;}a[maxn];
int n,m,x,y,z,tot,cnt;
int fa[maxn],fq[maxn],d[maxn],son[maxn],size[maxn],last[maxn],len[maxn],mx[maxn],w[maxn],ans[maxn],top[maxn];
bool ty[maxn];
void read(int &k)
{
int f=;k=;char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(c<=''&&c>='')k=k*+c-'',c=getchar();
k*=f;
}
bool cmp(poi a,poi b){return a.z<b.z;}
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
void add(int x,int y,int z){e[++tot].too=y;e[tot].dis=z;e[tot].pre=last[x];last[x]=tot;}
void dfs1(int x)
{
size[x]=;
for(int i=last[x];i;i=e[i].pre)
{
int too=e[i].too;
if(too==fq[x])continue;
fq[too]=x;
d[too]=d[x]+;
len[too]=e[i].dis;
dfs1(too);
if(size[too]>size[son[x]])son[x]=too;
size[x]+=size[too];
}
}
void dfs2(int x,int tp)
{
w[x]=++cnt;mx[cnt]=len[x];top[x]=tp;
if(son[x])dfs2(son[x],tp);
for(int i=last[x];i;i=e[i].pre)
if(e[i].too!=fq[x]&&e[i].too!=son[x])dfs2(e[i].too,e[i].too);
}
void pushup(int x,int l,int r)
{
if(l==r)return;
tree[x].min=min(tree[x<<].min,tree[x<<|].min);
tree[x].max=max(tree[x<<].max,tree[x<<|].max);
}
void pushdown(int x,int l,int r)
{
if(l==r)return;
if(tree[x].delta!=inf)
{
tree[x<<].min=min(tree[x<<].min,tree[x].delta);
tree[x<<|].min=min(tree[x<<|].min,tree[x].delta);
tree[x<<].delta=min(tree[x<<].delta,tree[x].delta);
tree[x<<|].delta=min(tree[x<<|].delta,tree[x].delta);
tree[x].delta=inf;
}
}
void build(int x,int l,int r)
{
if(l==r){tree[x].min=tree[x].delta=inf;tree[x].max=mx[l];return;}
int mid=(l+r)>>;
build(x<<,l,mid);build(x<<|,mid+,r);
tree[x].delta=inf;pushup(x,l,r);
}
void update(int x,int l,int r,int cl,int cr,int delta)
{
if(cl<=l&&r<=cr)tree[x].min=min(tree[x].min,delta),tree[x].delta=min(tree[x].delta,delta);
else
{
pushdown(x,l,r);
int mid=(l+r)>>;
if(cl<=mid)update(x<<,l,mid,cl,cr,delta);
if(cr>mid)update(x<<|,mid+,r,cl,cr,delta);
pushup(x,l,r);
}
}
int query(int x,int l,int r,int cx)
{
if(l==cx&&cx==r)return tree[x].min;
pushdown(x,l,r);
int mid=(l+r)>>,ret=inf;
if(cx<=mid)ret=query(x<<,l,mid,cx);
if(cx>mid)ret=query(x<<|,mid+,r,cx);
return ret;
}
int query2(int x,int l,int r,int cl,int cr)
{
if(cl<=l&&r<=cr)return tree[x].max;
pushdown(x,l,r);
int mid=(l+r)>>,ret=;
if(cl<=mid)ret=query2(x<<,l,mid,cl,cr);
if(cr>mid)ret=max(ret,query2(x<<|,mid+,r,cl,cr));
return ret;
}
int work(int x,int y,int delta)
{
int f1=top[x],f2=top[y],ans=;
while(f1!=f2)
{
if(d[f1]<d[f2])swap(x,y),swap(f1,f2);
if(delta!=-)update(,,n,w[f1],w[x],delta);
else ans=max(ans,query2(,,n,w[f1],w[x]));
x=fq[f1];f1=top[x];
}
if(x==y)return ans;
if(d[x]<d[y])swap(x,y);
if(delta!=-)update(,,n,w[son[y]],w[x],delta);
else return max(ans,query2(,,n,w[son[y]],w[x]));
return ans;
}
int main()
{
read(n);read(m);
for(int i=;i<=m;i++)read(a[i].x),read(a[i].y),read(a[i].z),a[i].pos=i;
sort(a+,a++m,cmp);
for(int i=;i<=n;i++)fa[i]=i;
for(int i=;i<=m;i++)
{
int fx=gf(a[i].x),fy=gf(a[i].y);
if(fx==fy)continue;
add(a[i].x,a[i].y,a[i].z);
add(a[i].y,a[i].x,a[i].z);
fa[fx]=fy;ty[i]=;
}
dfs1();dfs2(,);build(,,n);
for(int i=;i<=m;i++)
if(!ty[i])
{
ans[a[i].pos]=work(a[i].x,a[i].y,-)-;
work(a[i].x,a[i].y,a[i].z);
}
for(int i=;i<=m;i++)if(ty[i])ans[a[i].pos]=query(,,n,w[d[a[i].x]>d[a[i].y]?a[i].x:a[i].y])-;
for(int i=;i<=m;i++)printf("%d ",ans[i]==inf-?-:ans[i]);
return ;
}

  求最大值还是用倍增,求最小值的话,上面两种方法都不够快…

  注意到每条边只会被能更新它的最小值更新一次,于是就可以上并查集跳跳跳了,复杂度O(N)

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#define ll long long
using namespace std;
const int maxn=,inf=2e9;
struct poi{int x,y,z,pos;}a[maxn],edge[maxn];
struct zs{int too,dis,pre;}e[maxn];
int n,m,x,y,z,tot,cnt,f1,f2,lastx,lasty;
int last[maxn],ans[maxn],mn[maxn][],mx[maxn][],f[maxn][],fa[maxn],d[maxn],v[maxn];
bool ty[maxn];
void read(int &k)
{
int f=;k=;char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(c<=''&&c>='')k=k*+c-'',c=getchar();
k*=f;
}
bool cmp(poi a,poi b){return a.z<b.z;}
void add(int x,int y,int z){e[++tot].too=y;e[tot].dis=z;e[tot].pre=last[x];last[x]=tot;}
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
inline void dfs(int x,int fa)
{
f[x][]=fa;d[x]=d[fa]+;
for(int i=last[x];i;i=e[i].pre)
if(e[i].too!=fa)
{
mx[e[i].too][]=e[i].dis;
dfs(e[i].too,x);
}
}
inline int query(int x,int y)
{
int ans=;
if(d[x]<d[y])swap(x,y);
for(int i=;i>=;i--)
if(d[f[x][i]]>=d[y])ans=max(ans,mx[x][i]),x=f[x][i];
if(x==y)return ans;
for(int i=;i>=;i--)
if(f[x][i]!=f[y][i])ans=max(ans,max(mx[x][i],mx[y][i])),x=f[x][i],y=f[y][i];
return max(ans,max(mx[x][],mx[y][]));
}
int main()
{
read(n);read(m);
for(int i=;i<=m;i++)read(a[i].x),read(a[i].y),read(a[i].z),a[i].pos=i;
for(int i=;i<=n;i++)fa[i]=i;
sort(a+,a++m,cmp);
for(int i=;i<=m;i++)
{
int fx=gf(a[i].x),fy=gf(a[i].y);
if(fx==fy)continue;
add(a[i].x,a[i].y,a[i].z);
add(a[i].y,a[i].x,a[i].z);
fa[fx]=fy;ty[i]=;
}
dfs(,);for(int j=;j<;j++)for(int i=;i<=n;i++)mx[i][j]=max(mx[i][j-],mx[f[i][j-]][j-]),f[i][j]=f[f[i][j-]][j-];
memset(ans,0x7f,sizeof(ans));
for(int i=;i<=m;i++)
if(!ty[i])
{
ans[a[i].pos]=query(a[i].x,a[i].y)-;
edge[++cnt].x=a[i].x;edge[cnt].y=a[i].y;edge[cnt].z=a[i].z;
}
sort(edge+,edge++cnt,cmp);
for(int i=;i<=n;i++)fa[i]=i;
for(int i=;i<=cnt;i++)
{
x=edge[i].x;y=edge[i].y;f1=gf(x);f2=gf(y);lastx=;lasty=;
while(f1!=f2)
{
if(d[f1]<d[f2])swap(x,y),swap(f1,f2),swap(lastx,lasty);
if(!v[x])
{
v[x]=i;
if(lastx)fa[lastx]=x;
}
else if(lastx)fa[lastx]=f1;
lastx=f1;x=f[f1][];f1=gf(x);
}
}
for(int i=;i<=m;i++)if(ty[i]&&v[d[a[i].x]>d[a[i].y]?a[i].x:a[i].y])ans[a[i].pos]=edge[v[d[a[i].x]>d[a[i].y]?a[i].x:a[i].y]].z-;
for(int i=;i<=m;i++)printf("%d ",ans[i]>=inf?-:ans[i]);
}

倍增+并查集: 浴谷夏令营例题Codeforces827DBest Edge Weight(三个愿望,一次满足~(大雾

倍增:             浴谷夏令营例题Codeforces827DBest Edge Weight(三个愿望,一次满足~(大雾

树链剖分:      浴谷夏令营例题Codeforces827DBest Edge Weight(三个愿望,一次满足~(大雾

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141361.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,067
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,504
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,312
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,307
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,904
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,097
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站