php 小企业网站 cms,百度关键词推广教程,全国建设厅网站,网站与平台的区别正题
题目链接:https://www.luogu.com.cn/problem/P4172 题目大意 nnn个点的一张图#xff0c;有两个操作
询问两个点之间的一条路径使得最长边最短删除一条边 解题思路
显然这条边一定是在最小生成树上的#xff0c;所以我们需要维护支持删边的最小生成树。
显然LCTLCTL…正题
题目链接:https://www.luogu.com.cn/problem/P4172 题目大意
nnn个点的一张图有两个操作
询问两个点之间的一条路径使得最长边最短删除一条边 解题思路
显然这条边一定是在最小生成树上的所以我们需要维护支持删边的最小生成树。
显然LCTLCTLCT无法支持删除但是注意到只有删除操作所以我们反着做的话就变成了加边操作用LCTLCTLCT维护即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includestack
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N2e510,inf2147483647;
int n,m,t,ans[N];
int from[N],w[N],val[N];
pairpairint,int ,intlk[N];
struct node{int x,y,w,id;bool del;
}e[N];
struct Query{int op,x,y;
}q[N];
struct LCT{stackint s;int fa[N],t[N][2],r[N];void PushUp(int x){from[x]x;w[x]val[x];if(t[x][0]w[t[x][0]]w[x])w[x]w[t[x][0]],from[x]from[t[x][0]];if(t[x][1]w[t[x][1]]w[x])w[x]w[t[x][1]],from[x]from[t[x][1]];return;}bool Nroot(int x){return fa[x](t[fa[x]][0]x||t[fa[x]][1]x);}bool Direct(int x){return t[fa[x]][1]x;}void Rev(int x){swap(t[x][0],t[x][1]);r[x]^1;}void PushDown(int x){if(r[x])Rev(t[x][0]),Rev(t[x][1]),r[x]0;return;}void Rotate(int x){int yfa[x],zfa[y];int xsDirect(x),ysDirect(y);int wt[x][xs^1];if(Nroot(y))t[z][ys]x;t[x][xs^1]y;t[y][xs]w;if(w)fa[w]y;fa[y]x;fa[x]z;PushUp(y);PushUp(x);}void Splay(int x){int nowx;s.push(x);while(Nroot(now))nowfa[now],s.push(now);while(!s.empty())PushDown(s.top()),s.pop();while(Nroot(x)){int yfa[x];if(!Nroot(y))Rotate(x);else if(Direct(x)Direct(y))Rotate(y),Rotate(x);else Rotate(x),Rotate(x);}return;}void Access(int x){for(int y0;x;yx,xfa[x])Splay(x),t[x][1]y,PushUp(x);return; }void MakeRoot(int x){Access(x);Splay(x);Rev(x);return;}void Split(int x,int y){MakeRoot(x);Access(y);Splay(y);return;}void Link(int x,int y){MakeRoot(x);fa[x]y;Access(x);return;}void Cut(int x,int y){MakeRoot(x);Access(y);Splay(y);fa[t[y][0]]0;t[y][0]0;PushUp(y);return;}
}LCT;
struct unionfind{int fa[N];int find(int x){return (fa[x]x)?x:(fa[x]find(fa[x]));}void unionn(int x,int y){int Fafind(x),Fbfind(y);if(xy)fa[y]x;else fa[x]y;return;}
}F;
bool CmP(node x,node y)
{return x.wy.w;}
bool cMp(node x,node y)
{return x.idy.id;}
int main()
{scanf(%d%d%d,n,m,t);for(int i1;im;i){scanf(%d%d%d,e[i].x,e[i].y,e[i].w);if(e[i].xe[i].y)swap(e[i].x,e[i].y);lk[i]mp(mp(e[i].x,e[i].y),i);e[i].idi;}sort(lk1,lk1m);for(int i1;it;i){scanf(%d%d%d,q[i].op,q[i].x,q[i].y);if(q[i].xq[i].y)swap(q[i].x,q[i].y);if(q[i].op2){q[i].x(*lower_bound(lk1,lk1m,mp(mp(q[i].x,q[i].y),0))).second;e[q[i].x].del1; } }for(int i1;inm;i)from[i]i,val[i]w[i]-inf;for(int i1;in;i)F.fa[i]i;for(int i1;im;i)val[in]w[in]e[i].w;sort(e1,e1m,CmP);for(int i1;im;i){if(e[i].del)continue;int FaF.find(e[i].x),FbF.find(e[i].y);if(FaFb)continue;F.unionn(Fa,Fb);LCT.Link(e[i].x,e[i].idn);LCT.Link(e[i].idn,e[i].y);}sort(e1,e1m,cMp);for(int it;i1;i--){if(q[i].op1){LCT.Split(q[i].x,q[i].y);ans[i]w[q[i].y];}else{int idq[i].x,x,y;ye[id].y;xe[id].x;LCT.Split(x,y);if(w[y]e[id].w){int wfrom[y];LCT.Cut(w,e[w-n].y);LCT.Cut(e[w-n].x,w);LCT.Link(x,idn);LCT.Link(idn,y);}}}for(int i1;it;i)if(q[i].op1)printf(%d\n,ans[i]);return 0;
}
