题意：有n个城市 ， 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, 0); vis[s] = 1; dist[s] = 0; queue<int> Q; Q.push(s); while( Q.size() ) { int p = Q.front(); Q.pop(); for(int i=1; i<=n; i++) { if( !G[p][i] )continue; if( !vis[i] ) { vis[i] = 1; dist[i] = dist[p] + 1; 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, 0); for(int i=1; i<n; i++) { scanf("%d %d", &a[i], &b[i]); G[a[i]][b[i]] = G[b[i]][a[i]] = 1; } int Ans = 0; for(int i=1; i<n; i++) { G[a[i]][b[i]] = G[b[i]][a[i]] = 0; met(dist, 0); Max = Index = 0; bfs(a[i]); bfs(Index); int ans = Max; met(dist, 0); Max = Index = 0; bfs(b[i]); bfs(Index); Ans = max(Ans, ans * Max); G[a[i]][b[i]] = G[b[i]][a[i]] = 1; } printf("%d\n", Ans); } return 0; }
