首页 > 代码库 > 14D-树形DP
14D-树形DP
找出树中2条不重复的路径使其路径长度乘积最大
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <vector>using namespace std;const int MAXN = 205;typedef pair<int,int> Edge;vector<Edge> adj[MAXN];bool del[MAXN];int st[MAXN], ed[MAXN];int n;void load() { scanf("%d", &n); for (int i = 1; i < n; ++i) { int a, b; scanf("%d%d", &a, &b); adj[a].push_back(make_pair(b,i)); adj[b].push_back(make_pair(a,i)); st[i] = a; ed[i] = b; }}int used[MAXN];int dis[MAXN];int farthest;void dfs(int u) { used[u] = true; for (vector<Edge>::iterator itr = adj[u].begin(); itr != adj[u].end(); ++itr) { int v = itr->first; int id = itr->second; if (0 == del[id] && 0 == used[v]) { dis[v] = dis[u]+1; if (dis[v] > dis[farthest]) farthest = v; dfs(v); } }}void work() { int ans = 0; for (int t= 1; t < n; ++t) { memset(used,0,sizeof(used)); memset(dis,0,sizeof(dis)); del[t] = true; farthest = st[t]; dfs(st[t]); memset(used,0,sizeof(used)); memset(dis,0,sizeof(dis)); dfs(farthest); int tans = dis[farthest]; memset(dis,0,sizeof(dis)); memset(used,0,sizeof(used)); farthest = ed[t]; dfs(ed[t]); memset(dis,0,sizeof(dis)); memset(used,0,sizeof(used)); dfs(farthest); tans *= dis[farthest]; if (tans > ans) ans = tans; del[t] = false; } printf("%d\n", ans);}int main() { load(); work(); return 0;}
14D-树形DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。