BZOJ2657 [ZJOI2012]旅游(journey)

2014.12.09 19:43 Tue| 9 visits oi_2015| 2015_刷题日常| Text

Solution

又是一道大浙江的省选题蛤……

对n边形进行三角剖分,恰好被n-3条连线分为n-2个三角形。看到这道题的第一反应是平面图最大流。后来发现确实应用到了类似的思想。在两个相邻的平面间连边,我们恰好可以得到一棵树,而最终答案就是树的直径。现在最为棘手的问题是如何在两个平面之间连边。显然,每一条边恰好被两个平面包含,这样可以输入时维护一个multimap(这里貌似是我想麻烦了?可以直接维护一个map,读入的同时判断并加边)。之后开心地跑两遍DFS就解决问题了哈!注意题目给出的三个点我们要先排一下序,便于后续操作。

Code

#include <bits/stdc++.h>
using namespace std;
#define N 200005

int n,root,dist[N];
int head[N],next[N*2],to[N*2],cnt;

multimap<pair<int,int>,int> m;
multimap<pair<int,int>,int>::iterator it;

bool check(int &x,int &y)
{
    if(y==x+1||(y==n&&x==1)) return false;
    return true;
}

inline void insert(int now,int x,int y,int z)
{
    if(x>y) swap(x,y); if(x>z) swap(x,z); if(y>z) swap(y,z);
    if(check(x,y)) m.insert(make_pair(pair<int,int>(x,y),now));
    if(check(y,z)) m.insert(make_pair(pair<int,int>(y,z),now));
    if(check(x,z)) m.insert(make_pair(pair<int,int>(x,z),now));
}

inline void add()
{
    int x=it->second,y=(++it)->second;
    to[++cnt]=y;
    next[cnt]=head[x]; head[x]=cnt;
    to[++cnt]=x;
    next[cnt]=head[y]; head[y]=cnt;
}

void dfs(int x)
{
    for(int i=head[x],y;i;i=next[i])
        if(!dist[y=to[i]])
            dist[y]=dist[x]+1, dfs(y);
}

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main()
{
    cin>>n;
    for(int i=1,x,y,z;i<=n-2;i++)
        x=read(),y=read(),z=read(),
        insert(i,x,y,z);
    for(it=m.begin();it!=m.end();++it) add();
    dfs(root=1);
    for(int i=2;i<=n;i++)
        if(dist[i]>dist[root])
            root=i;
    memset(dist,0,sizeof dist);
    dfs(root);
    for(int i=1;i<=n;i++)
        if(dist[i]>dist[root])
            root=i;
    cout<<dist[root]+1<<endl;
}