题解 P2610 【[ZJOI2012]旅游】

今天模拟赛考了这道题，那就来水一篇题解吧。。。（话说提高组模拟赛考什么省选题啊？？）

这道题要我们求一条线段最多能经过的三角形数量。

回想小学学过的奥数，老师告诉过我们这样一件事：`点无大小线无粗细`。

既然如此，为什么不能把这条线段看成一条巨大的把三角形看成点呢？

那么本题的思路就出来了：我们把三角形看成点，然后建立一颗二叉树，在树上跑两边BFS求直径就可以了。

可是为什么我们一定能建成二叉树呢？

其实很好证明。

三角形只有三条边，那么最多能有一个父亲和两个儿子，所以是二叉树。

当然，这个东西不是特别重要。

重点是，我们接下来怎么建图？

这里我是这样解决的：

先把每一条边都存进一个map里面，然后map手写结构体统计边出现的次数。

然后遍历一遍map，把所有出现不止一次的边两端的三角形连在一起。

这个办法唯一的问题是常数比较大，写的丑就容易TLE（然而机房的lemon竟然可以AC！）。

AC代码如下：

955ms 38272kb

 #include<bits/stdc++.h>

 using namespace std;

 namespace StandardIO{

     template<typename T>inline void read(T &x){

         x=;T f=;char c=getchar();

         for(;c<''||c>'';c=getchar())if(c=='-')f=-;

         for(;c>=''&&c<='';c=getchar())x=x*+c-'';

         x*=f;

     }

     template<typename T>inline void write(T x){

         if(x<)putchar('-'),x*=-;

         if(x>=)write(x/);

         putchar(x%+'');

     }

 }

 using namespace StandardIO;

 namespace Solve{

     const int N=;

     int n;

     struct __normal_pair{

         int first,second;

         inline bool operator < (const __normal_pair &x)const{

             if(first==x.first)return second<x.second;

             return first<x.first;

         }

     };

     struct __store_pair{

         int first,second,size;

         inline void push_back(int id){

             if(size++)second=id;

             else first=id;

         }

     };

     map<__normal_pair,__store_pair>edge;

     vector<int>graph[N];

     int dis[N],vis[N];

     inline __normal_pair make_pair(int f,int s){

         return (__normal_pair){f,s};

     }

     inline void sor(int &a,int &b,int &c){

         if(a>b)swap(a,b);

         if(a>c)swap(a,c);

         if(b>c)swap(b,c);

     }

     inline int bfs(int s,int time){

         queue<int>q;

         dis[s]=,vis[s]=time;

         q.push(s);

         int final;

         while(!q.empty()){

             final=q.front();q.pop();

             for(register vector<int>::iterator i=graph[final].begin();i!=graph[final].end();++i){

                 if(vis[*i]==time)continue;

                 vis[*i]=time,dis[*i]=dis[final]+;

                 q.push(*i);

             }

         }

         return final;

     }

     inline void solve(){

         read(n);

         for(register int i=;i<=n-;++i){

             int p,q,r;

             read(p),read(q),read(r);

             sor(p,q,r);

             edge[make_pair(p,q)].push_back(i);

             edge[make_pair(q,r)].push_back(i);

             edge[make_pair(p,r)].push_back(i);

         }

         for(register map<__normal_pair,__store_pair>::iterator i=edge.begin();i!=edge.end();++i){

             if(i->second.size>){

                 graph[i->second.first].push_back(i->second.second);

                 graph[i->second.second].push_back(i->second.first);

             }

         }

         write(dis[bfs(bfs(,),)]+);

     }

 }

 using namespace Solve;

 int main(){

 //    freopen("triangulation9.in","r",stdin);

 //    freopen("triangulation.out","w",stdout);

     solve();

 }

巴特西

题解 P2610 【[ZJOI2012]旅游】

最新文章

热门文章