【XSY2771】城市分治

题目描述

　　一个平原上有\(n\)个城市，第\(i\)个城市在点\((\cos \frac{2i\pi}{n},\sin \frac{2i\pi}{n})\)上。

　　每个城市和最近的两个城市有一条直线段的路。

　　此外，还有\(n-3\)条路，这些路不会和原有的路重合，这些路之间也不会相交。

　　通过每条道路均要花费\(1\)的时间。

　　每次给你两个城市，问你从一个城市到另一个城市最快要多久。

　　\(n\leq 100000\)

题解

　　先把图画出来，容易发现这是一个平面图，且这个图的对偶图是一棵树，每个点的度数不超过\(3\)。

　　那么我们可以对这棵树分治（点分治边分治都可以）。

　　每次选择一条边，对于每个询问，这个询问的最短路径可以经过这条边的两个端点，也可以不经过。

　　那么可以从这条边的两个端点开始BFS，并更新答案。

　　对于一个询问，如果这个询问的两个点不在这条边的同一侧，就可以把这个询问扔掉了，否则递归下去处理。

　　时间复杂度：\(O(n\log n)\)

代码

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<ctime>

#include<cstdlib>

#include<utility>

#include<vector>

#include<queue>

using namespace std;typedef long long ll;typedef pair<int,int> pii;void open(const char *s){

#ifndef ONLINE_JUDGE

char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);

#endif

}int rd(){int s,c;while((c=getchar())<'0'||c>'9');s=c-'0';while((c=getchar())>='0'&&c<='9')s=s*10+c-'0';return s;}

vector<int> g[100010];

int e[100010][3];

int qu[100010][3];

int c[100010];

int ti;

int tot;

int b[100010];

queue<int> q;

int num[100010];

int ans[100010];

int d[100010];

void bfs(int x)

{

	d[x]=0;

	q.push(x);

	ti++;

	b[x]=ti;

	while(!q.empty())

	{

		x=q.front();

		q.pop();

		for(auto v:g[x])

			if(c[v]==tot&&b[v]!=ti)

			{

				d[v]=d[x]+1;

				b[v]=ti;

				q.push(v);

			}

	}

}

int cnt;

int dist(int l,int r)

{

	if(r<l)

		r+=cnt;

	return r-l+1;

}

int belong(int l,int r,int x)

{

	if(l>r)

		r+=cnt;

	if(x<l)

		x+=cnt;

	return x<=r;

}

int belong2(int l,int r,int x)

{

	if(l>r)

		r+=cnt;

	if(x<=l)

		x+=cnt;

	return x<r;

}

void solve(vector<int> &id,vector<int> &qid)

{

	if(!qid.size())

		return;

	if(id.size()<=1)

		return;

	tot++;

	cnt=0;

	for(auto v:id)

	{

		c[v]=tot;

		num[v]=++cnt;

	}

	int s=0x7fffffff,x1,x2;

	for(auto v1:id)

		for(auto v2:g[v1])

			if(c[v2]==tot)

			{

				int v=max(dist(num[v1],num[v2]),dist(num[v2],num[v1]));

				if(v<s)

				{

					s=v;

					x1=v1;

					x2=v2;

				}

			}

	bfs(x1);

	for(auto v:qid)

		ans[v]=min(ans[v],d[qu[v][1]]+d[qu[v][2]]);

	bfs(x2);

	for(auto v:qid)

		ans[v]=min(ans[v],d[qu[v][1]]+d[qu[v][2]]);

	if(id.size()<=3)

		return;

	vector<int> id1,id2,qid1,qid2;

	for(auto v:id)

	{

		if(belong(num[x1],num[x2],num[v]))

			id1.push_back(v);

		if(belong(num[x2],num[x1],num[v]))

			id2.push_back(v);

	}

	for(auto v:qid)

	{

		if(belong2(num[x1],num[x2],num[qu[v][1]])&&belong2(num[x1],num[x2],num[qu[v][2]]))

			qid1.push_back(v);

		if(belong2(num[x2],num[x1],num[qu[v][1]])&&belong2(num[x2],num[x1],num[qu[v][2]]))

			qid2.push_back(v);

	}

	solve(id1,qid1);

	solve(id2,qid2);

}

int n,m;

int main()

{

	open("b");

	scanf("%d",&n);

	int x,y;

	for(int i=1;i<=n-3;i++)

	{

		scanf("%d%d",&x,&y);

		x++;

		y++;

		g[x].push_back(y);

		g[y].push_back(x);

		e[i][1]=x;

		e[i][2]=y;

	}

	for(int i=1;i<=n;i++)

	{

		g[i].push_back(i%n+1);

		g[i%n+1].push_back(i);

	}

	vector<int> id,qid;

	for(int i=1;i<=n;i++)

		id.push_back(i);

	scanf("%d",&m);

	for(int i=1;i<=m;i++)

	{

		scanf("%d%d",&qu[i][1],&qu[i][2]);

		qu[i][1]++;

		qu[i][2]++;

		qid.push_back(i);

		if(qu[i][1]==qu[i][2])

			ans[i]=0;

		else

			ans[i]=0x7fffffff;

	}

	solve(id,qid);

	for(int i=1;i<=m;i++)

		printf("%d\n",ans[i]);

	return 0;

}

巴特西

【XSY2771】城市分治

题目描述

题解

代码

最新文章

热门文章

巴特西

【XSY2771】城市 分治

题目描述

题解

代码

最新文章

热门文章

【XSY2771】城市分治