郑州达云通网站建设公司,网站seo诊断评分63,做网络课程的网站,济南建站推荐企汇优见效付款正题
P2387 题目大意
给你一个图#xff0c;每条边有两个全职a,b#xff0c;现在让你找一条从1到n的路径使得max(a)max(b)最小 解题思路
对a进行排序#xff0c;枚举a的最大值#xff0c;然后取b最小的边#xff0c;找1到n的最短路径
找最短路径可以用LCT求#xff0…正题
P2387 题目大意
给你一个图每条边有两个全职a,b现在让你找一条从1到n的路径使得max(a)max(b)最小 解题思路
对a进行排序枚举a的最大值然后取b最小的边找1到n的最短路径
找最短路径可以用LCT求对于连边如果不在一个连通分量内就直接连起来
否则在两个端点的路径上找一条最大的边将其断掉然后连上该边如果不是更优则不操作 code
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 100100
using namespace std;
ll n,m,g,x,y,now,ans,top,d[N1],v[N1];
struct line
{ll x,y,a,b;
}l[N];
bool cmp(line a,line b)
{return a.ab.a;
}
struct LCT
{#define ls son[x][0]#define rs son[x][1]ll p[N1],mx[N1],fa[N1],son[N1][2];bool NR(ll x){return fa[x](son[fa[x]][0]x||son[fa[x]][1]x);}bool IRS(ll x){return son[fa[x]][1]x;}void pushr(ll x){swap(ls,rs);p[x]^1;return;}void push_down(ll x){if(p[x]){if(ls)pushr(ls);if(rs)pushr(rs);p[x]0;}return;}void push_up(ll x){if(lsv[mx[ls]]v[mx[rs]]v[mx[ls]]v[x])mx[x]mx[ls];else if(rsv[mx[rs]]v[mx[ls]]v[mx[rs]]v[x])mx[x]mx[rs];else mx[x]x;return;}void rotate(ll x){ll yfa[x],zfa[y],kIRS(x),gson[x][!k];if(NR(y))son[z][IRS(y)]x;if(g)fa[g]y;son[x][!k]y;son[y][k]g;fa[x]z;fa[y]x;push_up(y);return;}void Splay(ll x){ll yx;d[top]y;while(NR(y))yfa[y],d[top]y;while(top)push_down(d[top--]);while(NR(x)){if(NR(fa[x])){if(IRS(x)IRS(fa[x]))rotate(fa[x]);else rotate(x);}rotate(x);}push_up(x);return;}void access(ll x){for(ll y0;x;xfa[yx])Splay(x),rsy,push_up(x);return;}void make_root(ll x){access(x);Splay(x);pushr(x);return;}ll find_root(ll x){access(x);Splay(x);while(ls)push_down(x),xls;Splay(x);return x;}void Split(ll x,ll y){make_root(x);access(y);Splay(y);return;}void link(ll x,ll y){make_root(x);if(find_root(y)!x)fa[x]y;return;}void cut(ll x,ll y){make_root(x);if(find_root(y)xfa[y]x!son[y][0]){rsfa[y]0;push_up(x);}return;}
}T;
int main()
{scanf(%lld%lld,n,m);for(ll i1;inm;i)T.mx[i]i;for(ll i1;im;i)scanf(%lld%lld%lld%lld,l[i].x,l[i].y,l[i].a,l[i].b);sort(l1,l1m,cmp);ll i1;ans1e15;while(im){gl[i].a;while(l[i].agim){xl[i].x;yl[i].y;v[in]l[i].b;if(T.find_root(x)T.find_root(y)){T.Split(x,y);nowT.mx[y];if(v[now]l[i].b){T.cut(l[now-n].x,now);T.cut(l[now-n].y,now);T.link(x,in);T.link(y,in);}}else{T.link(x,in);T.link(y,in);}i;}if(T.find_root(1)T.find_root(n)){T.Split(1,n);ansmin(ans,gv[T.mx[n]]);}}if(ans1e15)printf(%lld,ans);else puts(-1);return 0;
}
