首页 > 代码库 > bzoj3051: [wc2013]平面图
bzoj3051: [wc2013]平面图
Description
Input
Output
扫描线求出平面图的对偶图然后求最小生成树,用并查集按秩合并,以便查询两点间路径最大权
#include<stdio.h>#include<algorithm>#include<vector>#include<set>#include<cmath>int f[200007],f2[200007],h2[200007];int get(int*f,int x){ int a=x,c; while(x!=f[x])x=f[x]; while(x!=f[a])c=f[a],f[a]=x,a=c; return x;}int get2(int x){ while(x!=f2[x])x=f2[x]; return x;}void merge(int a,int b){ a=get(f,a);b=get(f,b); if(a<b)f[b]=a; else f[a]=b;}double X;struct ln{ double k,b;int id; double operator()(double x)const{return k*x+b;} bool operator<(ln w)const{return operator()(X)+1e-8<w(X);}};std::set<ln>line;struct pos{ double x,y; void R(){ scanf("%lf%lf",&x,&y); }}ps[100007],qs[100007][2];struct dir{ double d; int i1,i2; bool operator<(dir w)const{return d<w.d;}};std::vector<dir>vs[100007];struct ev{ int t; double x; int w; bool operator<(ev a)const{return x!=a.x?x<a.x:t<a.t;}}e[500007];int ep=0,ee[200007];int n,m,q;struct edge{ int a,b,c,ID; ln l; void R(int I){ ID=I; scanf("%d%d%d",&a,&b,&c); if(ps[a].x>ps[b].x)std::swap(a,b); if(ps[a].x!=ps[b].x){ e[ep++]=(ev){1,ps[a].x,I}; e[ep++]=(ev){0,ps[b].x,I}; double k=(ps[b].y-ps[a].y)/(ps[b].x-ps[a].x); l=(ln){k,ps[a].y-ps[a].x*k,I}; } vs[a].push_back((dir){atan2(ps[b].y-ps[a].y,ps[b].x-ps[a].x),I,I+m}); vs[b].push_back((dir){atan2(ps[a].y-ps[b].y,ps[a].x-ps[b].x),I+m,I}); } bool operator<(const edge&w)const{return c<w.c;}}es[100007];int ws[100007][2];void maxs(int&a,int b){if(a<b)a=b;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m*2;++i)f[i]=f2[i]=i; for(int i=1;i<=n;++i)ps[i].R(); for(int i=1;i<=m;++i)es[i].R(i); scanf("%d",&q); for(int i=1;i<=q;++i){ qs[i][0].R(); qs[i][1].R(); e[ep++]=(ev){2,qs[i][0].x,i}; e[ep++]=(ev){3,qs[i][1].x,i}; } std::sort(e,e+ep); e[ep].x=e[ep-1].x+10000; double x0=e[0].x-10000,x1; for(int i=0,j=0;i<ep;){ x1=e[i].x; for(;j<ep&&e[j].x==x1;++j); X=(x0+x1)/2.; for(;i<j&&e[i].t==0;++i){ std::set<ln>::iterator it=line.find(es[e[i].w].l); line.erase(it); } X=(x1+e[j].x)/2.; for(int k=i;k<j&&e[k].t==1;++k){ ln w=es[e[k].w].l; line.insert(w); } for(;i<j&&e[i].t==1;++i){ ln w=es[e[i].w].l; std::set<ln>::iterator it=line.find(w); ++it; if(it==line.end())merge(0,e[i].w+m); else merge(e[i].w+m,it->id); --it; if(it==line.begin())merge(0,e[i].w); else --it,merge(e[i].w,it->id+m); } X=x1; for(;i<j;++i){ ln w=(ln){0,qs[e[i].w][e[i].t-2].y,0}; std::set<ln>::iterator it=line.lower_bound(w); if(it!=line.end())ws[e[i].w][e[i].t-2]=it->id; } x0=x1; } for(int i=1;i<=n;++i)if(!vs[i].empty()){ std::sort(vs[i].begin(),vs[i].end()); vs[i].push_back(vs[i][0]); for(int j=1;j<vs[i].size();++j){ merge(vs[i][j-1].i2,vs[i][j].i1); } } std::sort(es+1,es+m+1); for(int i=1;i<=m;++i){ int x=get2(get(f,es[i].ID)); int y=get2(get(f,es[i].ID+m)); if(x&&y&&x!=y){ if(h2[x]<h2[y])f2[x]=y,ee[x]=es[i].c; else{ if(h2[x]==h2[y])++h2[x]; f2[y]=x;ee[y]=es[i].c; } } } for(int i=1;i<=q;++i){ int x=get(f,ws[i][0]),y=get(f,ws[i][1]); if(!x||!y)puts("-1"); else{ int v=0; while(x!=y){ if(h2[x]>h2[y])std::swap(x,y); maxs(v,ee[x]); x=f2[x]; } printf("%d\n",v); } } return 0;}
bzoj3051: [wc2013]平面图
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。