UOJ Logo zgjkt的博客

博客

【bzoj2657】旅游

2015-11-30 13:47:27 By zgjkt

题目大意

给出一个凸$n$边形,按顺时针给予顶点编号为$[1,n]$

如今把这个凸$n$边形划分成$n-2$个三角形,给出这些三角形的三个顶点编号

询问两个不相邻顶点间的路径最多可以经过多少个三角形(路径中包含一个三角形的一条边视作经过这个三角形)

数据范围

$4\leqslant n\leqslant 200000$


题解

跑暴力强行搜索肯定不能通过这道题的,因此我们要转换一下建图的方法

我们想到如果是一个凸$n$边形划分成的三角形,把它视作顶点,邻边视作连接两个相邻三角形的边,那么原图就肯定可以转化为一棵树

然后跑一遍树的直径即可


程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
using namespace std;
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-48;ch=getchar();}
    return x*f;
}

int n,dia,et,top;
struct side{int mn,mx,id;}s[600500];
struct edge{int to,next;}e[400500];
int last[200500];
inline int cmp(side a,side b){return a.mn==b.mn?a.mx<b.mx:a.mn<b.mn;}
inline void insert(int a,int b,int id){s[++top]=(side){min(a,b),max(a,b),id};}
inline void addedge(int u,int v){
    e[++et]=(edge){v,last[u]};last[u]=et;
    e[++et]=(edge){u,last[v]};last[v]=et;
}

int dfs(int x,int fa){
    int mx1=0,mx2=0;
    goedge(i,x){
        if (e[i].to==fa) continue;
        int sum=dfs(e[i].to,x)+1;
        if (sum>mx1) mx2=mx1,mx1=sum;
        else if (sum>mx2) mx2=sum;
    }
    if (dia<mx1+mx2) dia=mx1+mx2;
    return mx1;
}

int main(){
    n=read();
    For(i,1,n-2){
        int p=read(),q=read(),r=read();
        insert(p,q,i);insert(p,r,i);insert(q,r,i);
    }
    sort(s,s+top+1,cmp);
    For(i,2,top)
        if (s[i].mn==s[i-1].mn&&s[i].mx==s[i-1].mx) addedge(s[i].id,s[i-1].id);
    dfs(1,0);
    printf("%d\n",dia+1);
    return 0;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。