题目描述
到了难得的暑假,为了庆祝小白在数学考试中取得的优异成绩,小蓝决定带小白出去旅游~~
经过一番抉择,两人决定将T国作为他们的目的地。T国的国土可以用一个凸N边形来表示,N个顶点表示N个入境/出境口。T国包含N-2个城市,每个城市都是顶点均为N边形顶点的三角形(换而言之,城市组成了关于T国的一个三角剖分)。两人的旅游路线可以看做是连接N个顶点中不相邻两点的线段。
为了能够买到最好的纪念品,小白希望旅游路线上经过的城市尽量多。作为小蓝的好友,你能帮帮小蓝吗?
输入格式
每个输入文件中仅包含一个测试数据。
第一行包含两个由空格隔开的正整数N,N的含义如题目所述。
接下来有N-2行,每行包含三个整数 p,q,r,表示该城市三角形的三个顶点的编号(T国的N个顶点按顺时间方向从1至n编号)。
输出格式
输出文件共包含1行,表示最多经过的城市数目。(一个城市被当做经过当且仅当其与线路有至少两个公共点)
题目解析
一开始还以为是计算几何,后来觉得这种不定形状的还是应该用图论解决。
解决此题,需要挖掘三角剖分的性质,一个三角剖分可以把一个凸边形划分成
个区域,在凸
边形内部应有
条边。如果我们把每个城市当做一个点,相邻的区域连上一条边,毫无疑问,这样构成的图是连通的。所以这是一棵树。
转化成一棵树后问题便清晰了,题目所求即是树的直径。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
/************************************************************** Problem: 2657 User: frank_c1 Language: C++ Result: Accepted Time:1356 ms Memory:64556 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ struct edge { int next,to; }; const int maxn=(int)(2e5)+5; const int mo=5000000; int fr[maxn]; int d[maxn]; LL key[mo]; int val[mo]; edge e[maxn<<1]; int n,tote=0; inline void addone(int u,int v) { ++tote; e[tote].next=fr[u];fr[u]=tote;e[tote].to=v; } inline void addedge(int u,int v) { addone(u,v);addone(v,u); } inline LL idx(LL a,LL b) {return a*n+b;} inline void check(int a,int b,int x) { LL k=idx(a,b),p=k % mo; while(key[p]!=0 && key[p]!=k) p=(p+1) % mo; if(key[p]==k) addedge(val[p],x); else key[p]=k,val[p]=x; } queue<int> Q; inline int bfs(int s) { memset(d,-1,sizeof(d)); int res=s; d[s]=0; Q.push(s); while(!Q.empty()) { int x=Q.front();Q.pop(); RAL(i,x) if(d[e[i].to]==-1) { d[e[i].to]=d[x]+1; Q.push(e[i].to); if(d[e[i].to]>d[res]) res=e[i].to; } } return res; } int main() { int a,b,c; read(n); memset(fr,-1,sizeof(fr)); REP(i,1,n-2) { read(a);read(b);read(c); if(b<a) swap(a,b); if(c<a) swap(a,c); if(c<b) swap(b,c); check(a,b,i);check(a,c,i);check(b,c,i); } int s=bfs(1); printf("%d\n",d[bfs(s)]+1); return 0; } |