@Jerusalem 2016-02-02T19:50:07.000000Z 字数 1958 阅读 1344

Solution

### Vol 1

ZJOI2012 DAY1T2 旅游（Journey）

#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>#include <vector>using namespace std;const int maxn=200005;vector<int> G[maxn];int dis[maxn];int n;void AddEdge(int u,int v){    G[u].push_back(v);    G[v].push_back(u);}namespace GetEdge{    struct Edge{        int u,v;        int id;        Edge(){            u=v=0;            id=0;        }        Edge(int u_,int v_,int id_){            u=u_,v=v_;            id=id_;        }    };    vector<Edge> Cache;    bool CmpEdge(Edge a,Edge b)    {        return a.u==b.u?a.v<b.v:a.u<b.u;    }    void Solve()    {        sort(Cache.begin(),Cache.end(),CmpEdge);        for(int i=1;i<Cache.size();i++)            if(Cache[i].u==Cache[i-1].u&&Cache[i].v==Cache[i-1].v){                AddEdge(Cache[i].id,Cache[i-1].id); //              printf("%d %d\n",Cache[i].id,Cache[i-1].id);            }    }}void Sort(int &x,int &y,int &z)  {      int _x=min(min(x,y),z);      int _z=max(max(x,y),z);      int _y=x+y+z-_x-_z;      x=_x;y=_y;z=_z;  }  void ReadData(){    using namespace GetEdge;    scanf("%d",&n);    for(int i=1;i<=n-2;i++){        int a,b,c;        scanf("%d%d%d",&a,&b,&c);        Sort(a,b,c);        Cache.push_back(Edge(a,b,i));        Cache.push_back(Edge(a,c,i));         Cache.push_back(Edge(b,c,i));    }   }int GetFar(int u,int f,int& ans){    int tot=u,num;    dis[u]=1;    for(int i=0;i<G[u].size();i++){        int v=G[u][i];        if(v==f)            continue;        int cache=GetFar(v,u,num);        if(dis[u]<=num+1)            tot=cache;        dis[u]=max(dis[u],num+1);    }    ans=dis[u];    //cout<<ans<<endl;    return tot;}int GetDiameter(){    int crash;    int p=GetFar(1,-1,crash);    memset(dis,0,sizeof(dis));    GetFar(p,-1,crash);     return crash;}void Solve(){    GetEdge::Solve();    cout<<GetDiameter()<<endl;}void Close(){    fclose(stdin);    //fclose(stdout);}void Freopen(){    freopen("loli.in","r",stdin);}int main(){    Freopen();    ReadData();    Solve();    Close();    return 0;}

• 私有
• 公开
• 删除