自动搬运

查看原文

来自洛谷，原作者为

	Dr_Gears **

搬运于2025-08-24 21:39:38，当前版本为作者最后更新于2018-09-30 09:36:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先上结论

这道题仔细想想会发现，如果把每个三角形看作一个节点，领边看作一条边，那么最后生成的图一定是一个二叉树。 当然，其实二不二叉都不影响。 关键是如何证明这个结论。

然后上证明

嗯哼，这个道理其实很简单，但是我还是说一下。 首先，整个图是肯定联通的，毕竟本来就是一个多边形，它转换成图后肯定不存在独立的部分。 而且注意到一个特点，一个n边形能且只能分成n-2个三角形，且无论怎么分都只用连接n-3条对角线。 而在这道题中，每一条被连接起来的对角线，都等于生成图中的一条连边。 所以一共n-2个点，n-3条边。 再加上树上是不可能出现环的，而这道题中，如果形成了环，那肯定是一圈的三角形把一个点围了起来，然而节点都必须在边上，所以不可能形成环。 呐呐，由上可知证毕。 之后，我们知道了这是一个什么图，该思考怎样去算出答案。

注意到

我们的路线必须与一个城市至少有两个交点，才算是经过了这个城市，因此只经过一个顶点是没用的。 而且，我们的路线是一条线段，也就是说无法折返。由于这是一个凸多边形，至少不用担心走不过去的问题，那么问题就在于什么样的路线才是最优的。

又上结论

如果我们走生成图上的树的直径，那么一定是最优的。（你肯定知道树的直径是啥吧） 为什么？ 因为我们无法折返，就相当于在树上走一条简单路径，因此最长的路肯定就是直径辣。

如何实现

我们注意到n的范围是20万，有点大，显然用数组记录三角形的邻边是肯定会炸的。但是我们有STL啊！ 于是乎，pair套map映射就呼之欲出了。 至于如何找树的直径，那啥，直接O(n)dfs两遍就完事儿辣。如果不明白为什么。。。请百度（or谷歌）！。

最后上代码

#include<bits/stdc++.h>
#define fr(i,a,b) for(int i=a;i<=b;++i)
#define pr(i,a,b) for(int i=a;i>=b;--i)
#define fh(i,a,b) for(int i=head[a],b=e[i].to;i;i=e[i].last,b=e[i].to)
#define pp puts("")
#define xiu return
using namespace std;
typedef double lf;
typedef long long ll;
const int N = 2e5+10,M = 110,inf = 1e9+7;
const lf eps = 1e-5;
template <class T> void read(T &w){
	w=0;int f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){(w*=10)+=ch-'0';ch=getchar();}
	w*=f;
}

template <class T> void write(T w){
	if(w<0){putchar('-');w*=-1;}
	if(w/10) write(w/10);
	putchar(w%10+'0');
}
map <pair<int,int>,int> ys;
struct edg{int last,to;}e[N<<1];
int n,m,cur=1,head[N],deep[N],root,ans;
void add(int x,int y){
	e[++cur]=(edg){head[x],y};head[x]=cur;
	e[++cur]=(edg){head[y],x};head[y]=cur;
}
void dfs(int x,int y){
	deep[x]=deep[y]+1;
	fh(i,x,u){
		if(u==y) continue;
		dfs(u,x);
	}
}
int main(){
	read(n);
	fr(i,1,n-2){
		int p,q,r;
		read(p);read(q);read(r);
		if(q>p) swap(p,q);
		if(r>p) swap(p,r);
		if(r>q) swap(q,r);//那啥，排个序去重....少写了3个if+else，而且还省时间空间....
		if(!ys[pair<int,int>(p,q)]){
			ys[pair<int,int>(p,q)]=i;
		}
		else
			add(i,ys[pair<int,int>(p,q)]);
		if(!ys[pair<int,int>(p,r)]){
			ys[pair<int,int>(p,r)]=i;
		}
		else
			add(i,ys[pair<int,int>(p,r)]);
		if(!ys[pair<int,int>(q,r)]){
			ys[pair<int,int>(q,r)]=i;
		}
		else
			add(i,ys[pair<int,int>(q,r)]);
	}
	root=1;
	dfs(1,0);
	fr(i,2,n-2)
	if(deep[i]>deep[root])
		root=i;
	dfs(root,0);
	fr(i,1,n-2)
		if(deep[i]>ans)
		ans=deep[i];
	write(ans);pp;
	xiu 0;
}

哈哈一遍A无调试~