Solution

Vol 1

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;
}