D. Two Paths---cf14D（树的直径）

题目链接：http://codeforces.com/problemset/problem/14/D

题意：有n个city ; n-1条路：求断开一条路之后分成的两部分所构成的树的直径的积最大是多少；

n的取值范围不大，所以可以采用暴力枚举的方法’；

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <stdlib.h>

#include <queue>

#include <map>

using namespace std;

typedef long long LL;

#define met(a, b) memset(a, b, sizeof(a))

#define INF 0x3f3f3f3f

#define N 210

int G[N][N], n, vis[N], dist[N], Max, Index;

void bfs(int s)

{

    met(vis, );

    vis[s] = ;

    dist[s] = ;

    queue<int> Q;

    Q.push(s);

    while( Q.size() )

    {

        int p = Q.front();

        Q.pop();

        for(int i=; i<=n; i++)

        {

            if( !G[p][i] )continue;

            if( !vis[i] )

            {

                vis[i] = ;

                dist[i] = dist[p] + ;

                Q.push(i);

                if(dist[i] > Max)

                {

                    Max = dist[i];

                    Index = i;

                }

            }

        }

    }

}

int main()

{

    int a[N], b[N];

    while(scanf("%d", &n)!=EOF)

    {

        met(G, );

        for(int i=; i<n; i++)

        {

            scanf("%d %d", &a[i], &b[i]);

            G[a[i]][b[i]] = G[b[i]][a[i]] = ;

        }

        int Ans = ;

        for(int i=; i<n; i++)

        {

            G[a[i]][b[i]] = G[b[i]][a[i]] = ;

            met(dist, );

            Max = Index = ;

            bfs(a[i]);

            bfs(Index);

            int ans = Max;

            met(dist, );

            Max = Index = ;

            bfs(b[i]);

            bfs(Index);

            Ans = max(Ans, ans * Max);

            G[a[i]][b[i]] = G[b[i]][a[i]] = ;

        }

        printf("%d\n", Ans);

    }

    return ;

}