「BZOJ2960」跨平面 题解
对偶图+朱刘算法
Statement
输入第一行两个整数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