[关闭]
@Jerusalem 2016-02-02T11:50:07.000000Z 字数 1958 阅读 1118

Solution

Vol 1


ZJOI2012 DAY1T2 旅游(Journey)

链接:BZOJ2657

这是一道蛮有意思的题目。

题目是给出了一个凸多边形的三角剖分(Triangulation),要求从任意点出发,到达任意点,其间走的路径是对角线,且点不重复,求这条路径穿越过的三角形的最大可能数目。点的数目是20万。

这道题,我起初是从扫描线方向去思考,并没有什么成果。事实上这道题是一个很有意思的建模。

有一个结论,它是说:任意三角剖分,把三角区域视作点,把相邻三角区域连边,一定会形成一棵树。

首先,很显然这张图一定是连通的,如果不是树,就是说图上有环,那么这些环一定会包裹一个顶点,这与三角剖分的定义矛盾。

接下来,我画了几张图之后意识到,这棵树上两个点的简单路径经过的点,也就是用一条对角线把它们连接起来将会经过的三角区域。

这个结论是很直观的,因为连接两个三角区域时跨越的边也会在图上被跨越。

然后我们发现,题目就只是要求这棵树的直径,这是well-known的,到这里,我们就成功地完成了对问题的转化。

代码如下:

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <iostream>
  7. #include <vector>
  8. using namespace std;
  9. const int maxn=200005;
  10. vector<int> G[maxn];
  11. int dis[maxn];
  12. int n;
  13. void AddEdge(int u,int v)
  14. {
  15. G[u].push_back(v);
  16. G[v].push_back(u);
  17. }
  18. namespace GetEdge{
  19. struct Edge{
  20. int u,v;
  21. int id;
  22. Edge(){
  23. u=v=0;
  24. id=0;
  25. }
  26. Edge(int u_,int v_,int id_){
  27. u=u_,v=v_;
  28. id=id_;
  29. }
  30. };
  31. vector<Edge> Cache;
  32. bool CmpEdge(Edge a,Edge b)
  33. {
  34. return a.u==b.u?a.v<b.v:a.u<b.u;
  35. }
  36. void Solve()
  37. {
  38. sort(Cache.begin(),Cache.end(),CmpEdge);
  39. for(int i=1;i<Cache.size();i++)
  40. if(Cache[i].u==Cache[i-1].u&&Cache[i].v==Cache[i-1].v){
  41. AddEdge(Cache[i].id,Cache[i-1].id);
  42. // printf("%d %d\n",Cache[i].id,Cache[i-1].id);
  43. }
  44. }
  45. }
  46. void Sort(int &x,int &y,int &z)
  47. {
  48. int _x=min(min(x,y),z);
  49. int _z=max(max(x,y),z);
  50. int _y=x+y+z-_x-_z;
  51. x=_x;y=_y;z=_z;
  52. }
  53. void ReadData()
  54. {
  55. using namespace GetEdge;
  56. scanf("%d",&n);
  57. for(int i=1;i<=n-2;i++){
  58. int a,b,c;
  59. scanf("%d%d%d",&a,&b,&c);
  60. Sort(a,b,c);
  61. Cache.push_back(Edge(a,b,i));
  62. Cache.push_back(Edge(a,c,i));
  63. Cache.push_back(Edge(b,c,i));
  64. }
  65. }
  66. int GetFar(int u,int f,int& ans)
  67. {
  68. int tot=u,num;
  69. dis[u]=1;
  70. for(int i=0;i<G[u].size();i++){
  71. int v=G[u][i];
  72. if(v==f)
  73. continue;
  74. int cache=GetFar(v,u,num);
  75. if(dis[u]<=num+1)
  76. tot=cache;
  77. dis[u]=max(dis[u],num+1);
  78. }
  79. ans=dis[u];
  80. //cout<<ans<<endl;
  81. return tot;
  82. }
  83. int GetDiameter()
  84. {
  85. int crash;
  86. int p=GetFar(1,-1,crash);
  87. memset(dis,0,sizeof(dis));
  88. GetFar(p,-1,crash);
  89. return crash;
  90. }
  91. void Solve()
  92. {
  93. GetEdge::Solve();
  94. cout<<GetDiameter()<<endl;
  95. }
  96. void Close()
  97. {
  98. fclose(stdin);
  99. //fclose(stdout);
  100. }
  101. void Freopen()
  102. {
  103. freopen("loli.in","r",stdin);
  104. }
  105. int main()
  106. {
  107. Freopen();
  108. ReadData();
  109. Solve();
  110. Close();
  111. return 0;
  112. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注