注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 3051 WC 2013 平面图(graph)  

2013-05-02 21:22:00|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
首先是平面图转对偶图
如何把块块找出来呢?白书上称之为“平面区域”算法。这个算法我在bzoj 1036 risk一题的题解中已经介绍过了
然后我们把域变成了点。然后对于一条边i,i所在的区域与i^1所在的区域(这是一个实现上的技巧,我们把边从2开始编号即可)之间连一条权值为i的权值的边,这样就实现了平面图转对偶图
接下来一步是点定位,我们先跳过
假设我们已经用一种神奇的算法(比如传说中的梯形剖分)完成了点定位问题,如何在logn的时间查询题目的那个问题呢?

经典问题:给定加权无向图的两个节点u,v,求出从u到v的一条路径,使得路径上的最长边最短
结论:求出加权无向图的最小生成树,则答案就是u到v这条路径上的最大边权。
证明:反证法。假设存在一条路径更优,我们把上面这个算法得到的那个边砍掉后树就变成了两部分;而更优的路径上显然有一条边能连接这两部分,于是得到了一棵更小的生成树
而求u到v这条路径上的最大边权,可以使用Tarjan来O(q)求,用link-cut-tree或倍增O(q log n)求。我个人觉得倍增法是最好写的
有关与倍增法可以参考郭华阳的国家集训队论文

现在就是点定位问题了……感谢CLJ大神在冬令营上讲的扫描线法
可是虽然大致思路懂了,真正写起来还是觉得完全不会写,于是膜拜了sillycross大神的论文,然后得到了ufo_go大神、sunzhouyi大神的教导……

扫描线法是这样子的
我们把所有点(包括线段上的点和题目输入的点)按横坐标排序(可以纵坐标但是接下来就要反着搞),然后按横坐标从小到大依次扫描所有点(接下来的边我们只考虑ax<bx即从左往右的边)
对于横坐标相同的同一列
先删除以这个横坐标上某个点为终点的边
再插入以这个横坐标上某个点为起点的边
对于在这个横坐标上的询问点,找到他上方的第一条线段(可以想象成是向上射射线遇到的第一条线段),这条线段所在的平面区域即为所求。
如何找呢?我们把它抽象成是一个平行于x轴的点,求前趋

于是有人问了,这个splay里维护的线段的<如何定义??
在sillycross大神的论文和ufo_go大神的教导下我明白了
定义一个全局变量x
对于线段a,b,如果在横坐标为x的时候a比b矮(即此时pa的纵坐标小于pb的纵坐标),认为a<b
x怎么看呢?
查询某个点前趋时,显然x=这个点的横坐标
插入某条线段时,x=当前区间的中点
删除某条线段时,x=上个区间的中点

然后是实现问题
这些可能都是因为个人写法原因导致的,不同的写法可能根本不会遇到我的这些问题。只是因为在调试中让我烦了很久才加上去的一些无厘头的话
比如我的区间的定义不是a[i].x与a[i+1].x,而是严格意义上的一段左右两边不想等的区间。为此我特地用了一个pre数组和一个next数组表示前(后)一个与他横坐标不同的点在哪里
释放内存是个好习惯,把每个块块保存下来虽然便于调试,但实在浪费了太多空间(我的程序就动不动被杀死被杀死被杀死)

感谢WJMZBMR、sillycross、pty的论文
感谢ufo_go和sunzhouyi和vfleaking对我在这道题的算法上的帮助
以下是很多调试信息都没删掉的程序……
这是我写过的最长的代码了
为什么我要去写这道题呢??
目的是:
以后遇到难写的题目我会暗示自己:我连平面图都写过……然后就有勇气去写了

不过第一次写这种超长代码的确是个挑战
记得我由于第一次写扫描线,结果那一百多行近两百行的代码改了又改删了又写的……
调起来也费劲
但这不是最麻烦的啊
最麻烦的是这题数据超级难出啊!!!
我一顿乱做数据,刚开始的时候爱心桃、五角星……………………
然后后来什么奇葩多边形都弄出来了
最后成功的解决了死循环
但是还是WA

最后过得也莫名其妙
我拿我那个WA掉的n<=2000的数据通过和暴力比较,发现我错的都是把-1的打成了有解的。然后我加了几个我个人觉得我已经判掉了的特判,终于终于终于过了!!!


#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<ctime>
#define maxn 400000
#define eps 1e-13
using namespace std;
int dcmp(double p)
{
	if(fabs(p)<eps)
		return 0;
	return p>eps?1:-1;
}
double nowx;
struct Point
{
	double x,y;
	int flag;
	Point()
	{
		flag=0;
	}
	Point(double x,double y): x(x),y(y) {}
	void Read()
	{
		scanf("%lf %lf",&x,&y);
	}
	friend Point operator + (const Point &a,const Point &b)
	{
		return Point(a.x+b.x,a.y+b.y);
	}
	friend Point operator - (const Point &a,const Point &b)
	{
		return Point(a.x-b.x,a.y-b.y);
	}
	friend Point operator * (const Point &a,double p)
	{
		return Point(a.x*p,a.y*p);
	}
	friend Point operator / (const Point &a,double p)
	{
		return Point(a.x/p,a.y/p);
	}
	friend bool operator < (const Point &a,const Point &b)
	{
		return dcmp(a.x-b.x)<0||(!dcmp(a.x-b.x)&&dcmp(a.y-b.y)<0);
	}
	friend bool operator != (const Point &a,const Point &b)
	{
		return dcmp(a.x-b.x)||dcmp(a.y-b.y);
	}
	friend bool operator == (const Point &a,const Point &b)
	{
		return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);
	}
}p[maxn];
typedef Point Vector;
double Cross(const Vector &a,const Vector &b)
{
	return a.x*b.y-a.y*b.x;
}
struct Seg
{
	Point a,b;
	Vector v;
	double rad;
	int pos,value;
	Seg() {}
	Seg(const Point &a,const Point &b): a(a),b(b)
	{
		v=b-a;
		rad=atan2(v.y,v.x);
		pos=0;
	}
	friend bool operator < (const Seg &a,const Seg &b)
	{
		return a.a<b.a||(a.a==b.a&&a.b<b.b);
	}
}S[maxn];
struct Polygon
{
	vector<Point> p;
	double area2;
	void Area()
	{
		area2=0;
		for(int i=1;i<p.size()-1;i++)
			area2=area2+Cross(p[i]-p[0],p[i+1]-p[0]);
	}
	void print()
	{
		for(int i=0;i<p.size();i++)
			printf("(%.1lf;%.1lf) ",p[i].x,p[i].y);
		printf("\n");
	}
};
int n,m,tot=1,nFace,Forbid;
vector<Seg> edge[maxn];
map<Seg,int> hash_Seg;
bool cmp_rad(const Seg &a,const Seg &b)
{
	return a.rad<b.rad;
}
void read()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
		p[i].Read();
	for(int i=1,a,b,v;i<=m;i++)
	{
		scanf("%d %d %d",&a,&b,&v);
		Seg S1=Seg(p[a],p[b]);
		Seg S2=Seg(p[b],p[a]);
		S1.value=v,S2.value=v;
		hash_Seg[S1]=++tot,S[tot]=S1;
		hash_Seg[S2]=++tot,S[tot]=S2;
		edge[a].push_back(S1),edge[b].push_back(S2);
	}
}
void Find_Polygon()
{
	static int next[maxn];
	for(int i=1;i<=n;i++)
		sort(edge[i].begin(),edge[i].end(),cmp_rad);
	for(int i=1;i<=n;i++)
		for(int j=0;j<edge[i].size();j++)
		{
			Seg a=edge[i][j],b=edge[i][(j+1)%edge[i].size()];
			int x=hash_Seg[a],y=hash_Seg[b];
			next[x]=y;
		}
	static Polygon poly;
	for(int i=2;i<=tot;i++)
		if(S[i].pos==0)
		{
			int x=i;
			poly.p.clear();
			++nFace;
			do
			{
				poly.p.push_back(S[x].a);
				S[x].pos=nFace;
				x=next[x^1];
			}while(x!=i);
			poly.Area();
			if(dcmp(poly.area2)>=0)
				Forbid=nFace;
			/*{
				Forbid=nFace;
				printf("%d : \n",nFace);
			}
			else
			{
				printf("%d : ",nFace);
				poly.print();
			}*/
		}
	for(int i=1;i<=n;i++)
		edge[i].clear();
	n=nFace,m=tot;
	/*for(int i=1;i<=n;i++)
	{
		printf("%d : ",i);
		for(int j=0;j<graph[i].p.size();j++)
			printf("(%.1lf;%.1lf) ",graph[i].p[j].x,graph[i].p[j].y);
		printf("\n");
	}*/
}
struct Edge
{
	int u,v,dis;
	friend bool operator < (const Edge &a,const Edge &b)
	{
		return a.dis<b.dis;
	}
};
struct Set
{
	int father[maxn],dep[maxn],n;
	Set() {}
	Set(int n): n(n)
	{
		for(int i=1;i<=n;i++)
			father[i]=i,dep[i]=0;
	}
	int Find(int p)
	{
	 	if(father[p]!=p)
			father[p]=Find(father[p]);
		return father[p];
	}
	void merge(int a,int b)
	{
		a=Find(a),b=Find(b);
		if(dep[a]>dep[b])
			swap(a,b);
		father[a]=b;
		if(dep[a]==dep[b])
			dep[b]++;
	}
};
int F[maxn][22],value[maxn][22],dep[maxn];
void make_Mst()
{
	static Set temp=Set(n);
	static Edge edge[maxn];
	int tot=0;
	int nedge=0;
	static int to[maxn],next[maxn],len[maxn],start[maxn];
	for(int i=2;i<=m;i+=2)
		if(S[i].pos!=S[i^1].pos&&S[i].pos!=Forbid&&S[i^1].pos!=Forbid)
		{
			tot++;
			edge[tot].u=S[i].pos,edge[tot].v=S[i^1].pos,edge[tot].dis=S[i].value;
		}
	sort(edge+1,edge+tot+1);
	for(int i=1;i<=tot;i++)
	{
		int x=temp.Find(edge[i].u),y=temp.Find(edge[i].v);
		if(x==y)
			continue;
		temp.merge(x,y);
		nedge++,to[nedge]=y,next[nedge]=start[x],len[nedge]=edge[i].dis,start[x]=nedge;
		nedge++,to[nedge]=x,next[nedge]=start[y],len[nedge]=edge[i].dis,start[y]=nedge;
	}
	static int queue[maxn];
	int front=0,rear=1;
	for(int i=1;i<=n;i++)
		dep[i]=-1;
	queue[rear]=Forbid==1?2:1,dep[queue[rear]]=1;
	while(front<rear)
	{
		int p=queue[++front];
		for(int i=start[p];i;i=next[i])
			if(dep[to[i]]==-1)
			{
				dep[to[i]]=dep[p]+1;
				queue[++rear]=to[i];
				F[to[i]][0]=p,value[to[i]][0]=len[i];
			}
	}
	for(int j=1;j<=20;j++)
		for(int i=1;i<=n;i++)
			if(i!=Forbid)
			{
				F[i][j]=F[F[i][j-1]][j-1];
				value[i][j]=max(value[i][j-1],value[F[i][j-1]][j-1]);
			}
}
int solve(int x,int y)
{
	if(x==y)
		return 0;
 	if(dep[x]<dep[y])
	 	swap(x,y);
 	int ans=0;
 	for(int i=20;i>=0;i--)
	 	if(dep[F[x][i]]>=dep[y])
	 	{
			ans=max(ans,value[x][i]);
		 	x=F[x][i];
		}
	for(int i=20;i>=0;i--)
		if(F[x][i]!=F[y][i])
		{
			ans=max(ans,max(value[x][i],value[y][i]));
			x=F[x][i],y=F[y][i];
		}
	if(x!=y)
		ans=max(ans,max(value[x][0],value[y][0]));
	return ans;
}
struct Node
{
	Point a,b;
	Vector v;
	int pos;
	Node() {}
	Node(const Point &a,const Point &b): a(a),b(b)
	{
		v=b-a;
	}
	friend Point Get_Inter(const Node &a,const Node &b)
	{
		Vector v=a.a-b.a;
		double t=Cross(b.v,v)/Cross(a.v,b.v);
		return a.a+a.v*t;
	}
	friend bool operator < (const Node &a,const Node &b)
	{
		Node Y;
		Y=Node(Point(nowx,0),Point(nowx,1));
		Point pa=!dcmp(Cross(a.v,Y.v))?a.a:Get_Inter(a,Y);
		Point pb=!dcmp(Cross(b.v,Y.v))?b.a:Get_Inter(b,Y);
		return dcmp(pa.y-pb.y)<0;
	}
	friend bool operator == (const Node &a,const Node &b)
	{
		return a.a==b.a&&a.b==b.b;
	}
};
map<Point,int> hash_Point;
vector<int> to1[maxn],to2[maxn];
struct SplayTree
{
	int root,stack[maxn],top,son[maxn][2],father[maxn];
	Node v[maxn];
	SplayTree()
	{
		for(int i=maxn-10;i>=1;i--)
			stack[++top]=i;
	}
	void Rotate(int p,int x)
	{
		int mark=p==son[x][1],y=son[p][mark^1],z=father[x];
		if(y!=0)
			father[y]=x;
		if(x==son[z][0])
			son[z][0]=p;
		if(x==son[z][1])
			son[z][1]=p;
		son[p][mark^1]=x,father[p]=z,son[x][mark]=y,father[x]=p;
	}
	void Splay(int p)
	{
		while(father[p])
		{
			int x=father[p],y=father[x];
			if(y==0)
				Rotate(p,x);
			else if((p==son[x][0])^(x==son[y][0]))
				Rotate(p,x),Rotate(p,y);
			else
				Rotate(x,y),Rotate(p,x);
		}
		root=p;
	}
	void Insert(const Node &k)
	{
		if(root==0)
		{
			root=stack[top--];
			v[root]=k;
			return ;
		}
		for(int i=root;;i=son[i][v[i]<k])
			if(son[i][v[i]<k]==0)
			{
				int p=stack[top--];
				son[i][v[i]<k]=p,father[p]=i,v[p]=k;
				Splay(p);
				return ;
			}
	}
	int Find(const Node &k)
	{
	 	for(int i=root;;i=son[i][v[i]<k])
		 	if(v[i]==k)
		 	{
				Splay(i);
				return i;
			}
	}
	void Delete(const Node &k)
	{
		int p=Find(k);
		if(son[p][0]==0&&son[p][1]==0)
			root=0;
		else if(son[p][0]==0&&son[p][1]!=0)
			father[root=son[p][1]]=0;
		else if(son[p][0]!=0&&son[p][1]==0)
			father[root=son[p][0]]=0;
		else
			for(int i=son[p][1];;i=son[i][0])
				if(son[i][0]==0)
				{
					son[i][0]=son[p][0],father[son[p][0]]=i,father[son[p][1]]=0;
					Splay(i);
					break;
				}
		stack[++top]=p;
		father[p]=son[p][0]=son[p][1]=0;
	}
	int lower(const Node &k)
	{
		int i;
		for(i=root;son[i][0];i=son[i][0]);
		if(k<v[i])
			return -1;
		for(i=root;son[i][1];i=son[i][1]);
		if(v[i]<k)
			return -1;
		Insert(k);
		Delete(v[root]);
		/* Because afther I Delete(root),the root is answer */
		return root==0||v[root].pos==Forbid?-1:v[root].pos;
	}
}tree;
void update(int ans[maxn][2],int p,int id)
{
	if(ans[id][0]==0)
		ans[id][0]=p;
	else
		ans[id][1]=p;
}
void Scan(Point p[],int ans[maxn][2],int n,Point a[])
{
	static int next[maxn],pre[maxn];
	a[0].x=a[1].x-1,a[n+1].x=a[n].x+1;
	for(int i=1;i<=n;i++)
		pre[i]=!dcmp(a[i].x-a[i-1].x)?pre[i-1]:i-1;
	for(int i=n;i>=1;i--)
		next[i]=!dcmp(a[i].x-a[i+1].x)?next[i+1]:i+1;
	for(int i=1;i<=n;i=next[i])
	{
		for(int k=i;k<next[i];k++)
			if(a[k].flag==0)
			{
				int x=hash_Point[a[k]];
				for(int j=0;j<to2[x].size();j++)
				{
					Point b=p[to2[x][j]];
					Seg s=Seg(a[k],b);
					int num=hash_Seg[s];
					Node temp;
					temp=Node(S[num].a,S[num].b);
					temp.pos=S[num].pos;
					if(dcmp(b.x-a[k].x)==0||temp.a<temp.b)
						continue;
					swap(temp.a,temp.b);
					nowx=(a[k].x+a[pre[k]].x)/2;
					tree.Delete(temp);
				}
			}
		for(int k=i;k<next[i];k++)
			if(a[k].flag==0)
			{
				int x=hash_Point[a[k]];
				for(int j=0;j<to1[x].size();j++)
				{
					Point b=p[to1[x][j]];
					Seg s=Seg(a[k],b);
					int num=hash_Seg[s];
					Node temp;
					temp=Node(S[num].a,S[num].b);
					temp.pos=S[num].pos;
					if(dcmp(b.x-a[k].x)==0||temp.b<temp.a)
						continue;
					nowx=(a[k].x+a[next[k]].x)/2;
					tree.Insert(temp);
				}
			}
		for(int k=i;k<next[i];k++)
			if(a[k].flag!=0)
			{
				Node temp=Node(Point(0,a[k].y),a[k]);
				temp.pos=0;
				nowx=a[k].x;
				update(ans,tree.lower(temp),a[k].flag);
			}
		//printf("%d\n",i);
	}
}
void Query()
{
	static Point p[maxn],temp[maxn];
	int id=0,q;
	for(int i=2;i<=m;i++)
	{
		Point a=S[i].a,b=S[i].b;
		if(!hash_Point.count(a))
		{
			hash_Point[a]=++id;
			p[id]=a;
		}
		if(!hash_Point.count(b))
		{
			hash_Point[b]=++id;
			p[id]=b;
		}
		int x=hash_Point[a],y=hash_Point[b];
		to1[x].push_back(y),to2[y].push_back(x);
	}
	scanf("%d",&q);
	Point ask;
	for(int i=1;i<=q;i++)
	{
		ask.Read();
		p[++id]=ask,p[id].flag=i;
		ask.Read();
		p[++id]=ask,p[id].flag=i;
	}
	for(int i=1;i<=id;i++)
		temp[i]=p[i];
	sort(temp+1,temp+id+1);
	static int pos[maxn][2];
	Scan(p,pos,id,temp);
	for(int i=1,ans;i<=q;i++)
	{
		if(pos[i][0]==-1||pos[i][1]==-1)
			ans=-1;
		else
			ans=solve(pos[i][0],pos[i][1]);
		if(ans==0&&pos[i][0]!=pos[i][1])
			ans=-1;
		printf("%d\n",ans);
	}
	/*for(int i=1;i<=q;i++)
		printf("%d %d\n",min(pos[i][0],pos[i][1]),max(pos[i][0],pos[i][1]));*/
}
int main()
{
	read();
	Find_Polygon();
	make_Mst();
	Query();
	//printf("%lf\n",(double)clock()/CLOCKS_PER_SEC);
	return 0;
}
/*
	ORZ vfleaking
	ORZ sunzhouyi
	ORZ ufo_go
	ORZ WJMZBMR
	ORZ sillycross
	ORZ pty
*/
  评论这张
 
阅读(1349)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017