记录编号	152803	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2012] 旅游	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.905 s
提交时间	2015-03-15 17:05:04	内存使用	12.33 MiB

/****************************************\
* Author : ztx
* Title  : [bzoj] 2657: [Zjoi2012]旅游(journey)
* ALG    :
画画图发现可以将每个三角形拆为三个三角形
他们代表相同的三角形,但是他们的关键字分别为三条边
这样的话按边排序就可以找到邻接关系并建树了
再对这棵树求最长链即可
暂时只想到了这么2B的解法
* CMT    :
* Time   :
\****************************************/
 
#include <cstdio>
#define Rep(i,l,r) for(i=l;i<=r;i++)
#define Rev(i,l,r) for(i=r;i>=l;i--)
int CH , NEG ;
template <typename TP>
inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>
inline void reads(TP& ret) {
	while (ret=getchar() , ret<'!') ;
	while (CH=getchar() , CH>'!') ;
}
 
#include <algorithm>
#include <queue>
 
#define  maxn  210010LL
#define  maxm  210010LL
 
struct FST { int to , next ; } e[maxm<<1] ;
int star[maxn] = {0} , tote = 1 ;
void AddEdge(int u , int v) { e[++tote].to = v ; e[tote].next = star[u] ; star[u] = tote ;  }
 
struct TAG { int a , b , id ; } A[maxn*3] ;
bool cmp(const TAG& a , const TAG& b) { return a.a==b.a?a.b<b.b:a.a<b.a; }
bool operator - (TAG& a , TAG& b) { return (a.a==b.a&&a.b==b.b) ; }
 
int n ;
std::queue<int>q ;
int dep[maxn] = {0} ;
 
int main() {
int i , a , b , c , p , tot = 0 ;
	#define READ
	#ifdef  READ
		freopen("journey.in" ,"r",stdin ) ;
		freopen("journey.out","w",stdout) ;
	#endif
	read(n) ;
	Rep (i , 1 , n-2) {
		read(a) , read(b) , read(c) ;
		if (a>b) {if (a>c) std::swap(a,c) ;}
		else if (b>c) std::swap(b,c) ;
/*
论
"
if (a>b) {if (a>c) std::swap(a,c) ;}
		else if (b>c) std::swap(b,c) ;
"
与
"
if (a>b) if (a>c) std::swap(a,c) ;
		else if (b>c) std::swap(b,c) ;
"
的区别 QAQ
*/
		if (a>b) std::swap(a,b) ;
		A[++tot] = (TAG){a,b,i} ;
		A[++tot] = (TAG){b,c,i} ;
		A[++tot] = (TAG){a,c,i} ;
	}
	std::sort(A+1 , A+tot+1 , cmp) ;
	Rep (i , 2 , tot) if (A[i]-A[i-1])
		AddEdge(A[i].id,A[i-1].id) ,
		AddEdge(A[i-1].id,A[i].id) ;
	q.push(1) ;
	dep[1] = -1 ;
	while (!q.empty()) {
		a = q.front() , q.pop() ;
		for (p=star[a];p;p=e[p].next)
			if (!dep[b=e[p].to]) {
				q.push(b) ; dep[b] = -1 ;
			}
	}
	q.push(a) ;
	dep[a] = 1 ;
	while (!q.empty()) {
		a = q.front() , q.pop() ;
		for (p=star[a];p;p=e[p].next)
			if (dep[b=e[p].to]==-1) {
				dep[b]=dep[a]+1 ;
				q.push(b) ;
			}
	}
	printf("%d\n", dep[a]) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}