首页 > 代码库 > 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]平面图