@Jerusalem
2016-02-02T19:50:07.000000Z
字数 1958
阅读 1393
Solution
ZJOI2012 DAY1T2 旅游(Journey)
链接:BZOJ2657
这是一道蛮有意思的题目。
题目是给出了一个凸多边形的三角剖分(Triangulation),要求从任意点出发,到达任意点,其间走的路径是对角线,且点不重复,求这条路径穿越过的三角形的最大可能数目。点的数目是20万。
这道题,我起初是从扫描线方向去思考,并没有什么成果。事实上这道题是一个很有意思的建模。
有一个结论,它是说:任意三角剖分,把三角区域视作点,把相邻三角区域连边,一定会形成一棵树。
首先,很显然这张图一定是连通的,如果不是树,就是说图上有环,那么这些环一定会包裹一个顶点,这与三角剖分的定义矛盾。
接下来,我画了几张图之后意识到,这棵树上两个点的简单路径经过的点,也就是用一条对角线把它们连接起来将会经过的三角区域。
这个结论是很直观的,因为连接两个三角区域时跨越的边也会在图上被跨越。
然后我们发现,题目就只是要求这棵树的直径,这是well-known的,到这里,我们就成功地完成了对问题的转化。
代码如下:
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int maxn=200005;
vector<int> G[maxn];
int dis[maxn];
int n;
void AddEdge(int u,int v)
{
G[u].push_back(v);
G[v].push_back(u);
}
namespace GetEdge{
struct Edge{
int u,v;
int id;
Edge(){
u=v=0;
id=0;
}
Edge(int u_,int v_,int id_){
u=u_,v=v_;
id=id_;
}
};
vector<Edge> Cache;
bool CmpEdge(Edge a,Edge b)
{
return a.u==b.u?a.v<b.v:a.u<b.u;
}
void Solve()
{
sort(Cache.begin(),Cache.end(),CmpEdge);
for(int i=1;i<Cache.size();i++)
if(Cache[i].u==Cache[i-1].u&&Cache[i].v==Cache[i-1].v){
AddEdge(Cache[i].id,Cache[i-1].id);
// printf("%d %d\n",Cache[i].id,Cache[i-1].id);
}
}
}
void Sort(int &x,int &y,int &z)
{
int _x=min(min(x,y),z);
int _z=max(max(x,y),z);
int _y=x+y+z-_x-_z;
x=_x;y=_y;z=_z;
}
void ReadData()
{
using namespace GetEdge;
scanf("%d",&n);
for(int i=1;i<=n-2;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
Sort(a,b,c);
Cache.push_back(Edge(a,b,i));
Cache.push_back(Edge(a,c,i));
Cache.push_back(Edge(b,c,i));
}
}
int GetFar(int u,int f,int& ans)
{
int tot=u,num;
dis[u]=1;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==f)
continue;
int cache=GetFar(v,u,num);
if(dis[u]<=num+1)
tot=cache;
dis[u]=max(dis[u],num+1);
}
ans=dis[u];
//cout<<ans<<endl;
return tot;
}
int GetDiameter()
{
int crash;
int p=GetFar(1,-1,crash);
memset(dis,0,sizeof(dis));
GetFar(p,-1,crash);
return crash;
}
void Solve()
{
GetEdge::Solve();
cout<<GetDiameter()<<endl;
}
void Close()
{
fclose(stdin);
//fclose(stdout);
}
void Freopen()
{
freopen("loli.in","r",stdin);
}
int main()
{
Freopen();
ReadData();
Solve();
Close();
return 0;
}