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 210int 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 ;
}