【题意】
一张无向图,每个边有两种边权,求1-n的路径中,经过两种边权最大值的和最小是多少
【分析】
这道题很巧妙地模仿了生成树的思想,先按照一个边权b排序,然后依次加入,这样能保证每一次的bi的最大值是不用计算的,就是当前加的bi值
只要维护ai最大值最小即可,所以我们利用LC不断加边,当x,y已经联通时,我们找到x-y路径中ai最大的一个,断开,再连上新的当前的x-y边
所以我们的LCT需要维护一个路径中的最大值出现在哪条边
【代码】
#include<bits/stdc++.h> using namespace std; int n,m; const int maxn=5e4+5; const int maxm=2e5+5; const int inf=0x3f3f3f3f; struct edge { int x,y,a,b; }e[maxm]; bool cmp(edge aa,edge bb) { return aa.b<bb.b; } int val[maxm],fa[maxm]; struct LCT { int son[2],v,maxi,rev,f; LCT() { f = son[0] = son[1] = rev = 0; } }tr[maxm]; #define ls(x) tr[x].son[0] #define rs(x) tr[x].son[1] int find(int x) { if(x==fa[x]) return x; return fa[x]=find(fa[x]); } int q[maxm],len; int isroot(int x) { return tr[x].f&&( ls(tr[x].f)==x || rs(tr[x].f)==x); } void pushup(int x) { tr[x].maxi=x; if(ls(x) && val[tr[ls(x)].maxi]>val[tr[x].maxi]) tr[x].maxi=tr[ls(x)].maxi; if(rs(x) && val[tr[rs(x)].maxi]>val[tr[x].maxi]) tr[x].maxi=tr[rs(x)].maxi; } void pushdown(int x) { if(!tr[x].rev) return; swap(ls(x),rs(x)); if(ls(x)) tr[ls(x)].rev^=1; if(rs(x)) tr[rs(x)].rev^=1; tr[x].rev^=1; } void rotate(int x) { int y =tr[x].f,z=tr[y].f,b=ls(y)==x?rs(x):ls(x); if (z && isroot(y)) (ls(z) == y ? ls(z) : rs(z)) = x; tr[x].f=z; tr[y].f=x; b?tr[b].f=y:0; if (ls(y) == x) rs(x)= y,ls(y)= b; else ls(x) = y, rs(y) = b; pushup(y); pushup(x); } int which(int x) { return x==rs(tr[x].f); } void splay(int x) { int i, y; q[len = 1] = x; for(int y=x;isroot(y);y=tr[y].f) q[++len]=tr[y].f; for(int i=len;i>=1;i--) pushdown(q[i]); while(isroot(x)) { if(isroot(tr[x].f)) { if (which(x) == which(tr[x].f)) rotate(tr[x].f); else rotate(x); } rotate(x); } pushup(x); } void access(int x) { for(int y=0;x;y=x,x=tr[x].f) { splay(x); rs(x)=y; if(y) tr[y].f=x; pushup(x); } } void makeroot(int x) { access(x); splay(x); tr[x].rev^=1; } void link(int x,int y) { makeroot(x); tr[x].f=y; } void cut(int x,int y) { makeroot(x); access(y); splay(y); tr[y].son[0]=0; tr[x].f=0; pushup(y); } int path(int x,int y) { makeroot(x); access(y); splay(y); return tr[y].maxi; } int main() { // freopen("forest.in","r",stdin); // freopen("forest.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].a,&e[i].b); sort(e+1,e+m+1,cmp); int ans=inf; for(int i=1;i<=m+n;i++) fa[i]=tr[i].maxi=i; for(int i=n+1;i<=n+m;i++) val[i]=e[i-n].a; for(int i=1;i<=m;i++) { int u=e[i].x,v=e[i].y,flag=1; if(find(u)==find(v)) { int maxi=path(u,v); if(val[maxi]>e[i].a) { cut(e[maxi-n].x,maxi); cut(maxi,e[maxi-n].y); } else flag=0; } else { int fx=find(u),fy=find(v); if(fx!=fy) fa[fx]=fy; } if(flag) { link(u,i+n); link(i+n,v); } if(find(1)==find(n)) ans=min(ans,e[i].b+val[path(1,n)]); } printf("%d\n",ans!=inf?ans:-1); return 0; }
吐槽:这道题目利用了并查集去加速判断,其实findroot也可,只是常数比较大,像这种只增加连通性的,最好都用并查集,有的题会卡一下下
这个并查集的fa和LCT的f一定要区分好,调了好久!!!