「BZOJ2960」跨平面 题解


对偶图+朱刘算法

Statement

img

输入第一行两个整数n和m,表示点与线段的数目。

接下来n行,每行两个整数x和y,表示第i个点的坐标,点从1到n编号。

接下来m行,每行四个整数p,q,V1和V2,表示存在一条从第p个点连向第q个点的线段,激活p->q这个方向的费用为V1,另一个方向费用为V2。

保证若两条线段相交,则交点是它们的公共端点。

输出一行一个正整数,表示最小总激活费用。

Solution

平面图转对偶图后便是裸的最小生成图了

转对偶图的难点在于找到一个多边形

我们考虑拆成两条边,意图让每一条有向边染色,使得同色的边顺次相连会包围出一个多边形

所以我们考虑每次找到一条尚未染色的边开始 dfs

先对每一条边按照其角度(斜率)排序

对于上一个点 \(fath\) ,当前走点 \(u\) ,我们意图找到一条边 \((u,v)\) ,使得上一条边是 \((u,fath)\)

因为事前排过序,所以这样会围出一个最小的多边形

同时由于我们拆出了两条边,所以不会出现一条边被染色两次的情况

转完对偶图,由于不定根,加一个超级根即可

注意题目保证有解

Code

#include
#define int long long
using namespace std;
const int N = 1e5+5;

char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){
    int s=0,w=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
    return s*w;
}
bool chkmin(int &a,int b){return a>b?a=b,1:0;}

namespace MST{
    struct Edge{int u,v,w;}edge[N];
    int pre[N],prv[N],vis[N],id[N];
    int n,cnt,rt,elen,ans,sum;

    void addedge(int u,int v,int w){edge[++elen]=(Edge){u,v,w};}
    int mst(){
        for(int i=1;i<=elen;++i)sum+=edge[i].w;
        for(int i=1;i<=n;++i)addedge(0,i,sum+1);
        rt=0,ans-=sum+1;
        while(1){
            for(int i=0;i<=n;++i)pre[i]=1e18;
            for(int i=1,u,v;u=edge[i].u,v=edge[i].v,i<=elen;++i)
                if(u!=v&&chkmin(pre[v],edge[i].w))prv[v]=u;
            memset(vis,-1,sizeof(vis)),memset(id,-1,sizeof(id)),cnt=pre[rt]=0;
            for(int i=0,v;i<=n;++i){
                ans+=pre[i],v=i;
                while(v!=rt&&id[v]==-1&&vis[v]!=i)vis[v]=i,v=prv[v];
                if(v!=rt&&id[v]==-1){
                    for(int u=prv[v];u^v;u=prv[u])id[u]=cnt;
                    id[v]=cnt++;
                }
            }
            if(!cnt)break;
            for(int i=0;i<=n;++i)if(id[i]==-1)id[i]=cnt++;
            for(int i=1,u,v;u=edge[i].u,v=edge[i].v,i<=elen;++i)
                edge[i].u=id[u],edge[i].v=id[v],edge[i].w-=(id[u]!=id[v])*pre[v];
            n=cnt-1,rt=id[rt];
        }
        return ans; 
    }
}
struct Edge{int u,v,nex,id,tp;}edge[N];
struct Line{
    int u,v,id,tp;double alpha;
    bool operator<(const Line&rhs)const{
        return alpha

相关