首页 > 代码库 > Codeforces 14D Two Paths 树的直径
Codeforces 14D Two Paths 树的直径
题目链接:点击打开链接
题意:给定一棵树
找2条点不重复的路径,使得两路径的长度乘积最大
思路:
1、为了保证点不重复,在图中删去一条边,枚举这条删边
2、这样得到了2个树,在各自的树中找最长链,即树的直径,然后相乘即可
#include<stdio.h> #include<iostream> #include<string.h> #include<set> #include<vector> #include<map> #include<math.h> #include<queue> #include<string> #include<stdlib.h> #include<algorithm> using namespace std; #define N 220 struct Edge { int from, to, nex; bool hehe; }edge[N<<1]; int head[N], edgenum; void add(int u, int v){ Edge E={u,v,head[u],true}; edge[edgenum] = E; head[u] = edgenum ++; } int n; int dis[N]; void init(){ memset(head, -1, sizeof head); edgenum = 0; } int bfs(int x){ memset(dis, 0, sizeof dis); dis[x] = 1; queue<int>q; q.push(x); int hehe = x; while(!q.empty()) { int u = q.front(); q.pop(); for(int i = head[u]; ~i; i = edge[i].nex) { if(!edge[i].hehe)continue; int v = edge[i].to; if(dis[v])continue; dis[v] = dis[u]+1, q.push(v); if(dis[hehe]<dis[v])hehe = v; } } return hehe; } int main(){ int i, u, v; while(~scanf("%d",&n)){ init(); for(i=1;i<n;i++){ scanf("%d %d",&u,&v); add(u,v); add(v,u); } int ans = 0; for(i = 0; i < edgenum; i+=2) { edge[i].hehe = edge[i^1].hehe = false; u = edge[i].from; v = edge[i].to; int L1 = bfs(u); int R1 = bfs(L1); int mul1 = dis[R1] -1; int L2 = bfs(v); int R2 = bfs(L2); int mul2 = dis[R2] -1; ans = max(ans, mul1 * mul2); edge[i].hehe = edge[i^1].hehe = true; } printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。