【BZOJ 2657】 [Zjoi2012]旅游(journey)

2657: [Zjoi2012]旅游(journey)Time Limit:5 SecMemory Limit:128 MBSubmit:546Solved:351[Submit][Status][Discuss]Description

到了难得的暑假，为了庆祝小白在数学考试中取得的优异成绩，小蓝决定带小白出去旅游~~

经过一番抉择，两人决定将T国作为他们的目的地。T国的国土可以用一个凸N边形来表示，N个顶点表示N个入境/出境口。T国包含N-2个城市，每个城市都是顶点均为N边形顶点的三角形(换而言之，城市组成了关于T国的一个三角剖分)。两人的旅游路线可以看做是连接N个顶点中不相邻两点的线段。

为了能够买到最好的纪念品，小白希望旅游路线上经过的城市尽量多。作为小蓝的好友，你能帮帮小蓝吗？

Input

每个输入文件中仅包含一个测试数据。

第一行包含两个由空格隔开的正整数N，N的含义如题目所述。

接下来有N-2行，每行包含三个整数p,q,r，，表示该城市三角形的三个顶点的编号(T国的N个顶点按顺时间方向从1至n编号)。

Output

输出文件共包含1行，表示最多经过的城市数目。(一个城市被当做经过当且仅当其与线路有至少两个公共点)

Sample Input

61 2 42 3 41 4 51 5 6

Sample Output

4

HINT

4<=N<=200000

巧妙的建图+树的直径~

有n-2个三角形，他们中间用n-3条边隔开，我们把三角形看作点，有公共边的三角形连边，就构成一棵树了！

因为树上两个点之间的边与图中两个三角形的公共边一一对应，因此在树上走一条边相当于在图中走一条公共边，；

而走一条公共边两个三角形都经过两次了，表示到达了两个城市。

所以问题就变成了求树的最长链即树的直径。

#include <iostream>#include <string>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <queue>#define M 250000#include <map>#define mp make_pairusing namespace std;int f[M],tot,h[M],n,d[M],a[5],ans,md[M];struct edge{int y,ne;}e[M*2];map<pair<int,int>,int> m;void Addedge(int x,int y){e[++tot].y=y;e[tot].ne=h[x];h[x]=tot;}void Solve(int k,int x,int y){int s=m[mp(x,y)];if (s)Addedge(k,s),Addedge(s,k),m.erase(m.find(mp(x,y)));else m[mp(x,y)]=k;}void Get(int x,int fa){md[x]=1;for (int i=h[x];i;i=e[i].ne){int y=e[i].y;if (y==fa) continue;Get(y,x);ans=max(ans,md[x]+md[y]);md[x]=max(md[x],md[y]+1);}}int main(){scanf("%d",&n);for (int i=1;i<=n-2;i++){scanf("%d%d%d",&a[1],&a[2],&a[3]);sort(a+1,a+1+3);Solve(i,a[1],a[2]);Solve(i,a[2],a[3]);Solve(i,a[1],a[3]);}Get(1,0);cout<<ans<<endl;return 0; }

RE是因为数组开小了！！

你可能付出一定的代价，但日后你得到的，远比付出的多得多。