題干：

鏈接：https://ac.nowcoder.com/acm/contest/369/C
來源：?？途W(wǎng)
?

小A給你了一棵樹，對(duì)于這棵樹上的每一條邊，你都可以將它復(fù)制任意（可以為0）次（即在這條邊連接的兩個(gè)點(diǎn)之間再加一條邊權(quán)相同的邊），求所有可能新形成的圖中歐拉路的最短長(zhǎng)度

歐拉路：從圖中任意一個(gè)點(diǎn)開始到圖中任意一個(gè)點(diǎn)結(jié)束的路徑，并且圖中每條邊只通過恰好一次

輸入描述:

第一行一個(gè)數(shù) n ，表示節(jié)點(diǎn)個(gè)數(shù)

接下來 n-1 行，每行三個(gè)整數(shù) u,v,w，表示有一條 u 到 v 邊權(quán)為 w 的無向邊

保證數(shù)據(jù)是一棵樹

輸出描述:

一行一個(gè)整數(shù)，表示答案

示例1

輸入

復(fù)制

4 1 2 1 1 3 1 1 4 2

輸出

復(fù)制

5

說明

一種可能的方案為復(fù)制 <1,2,1> 這條邊一次，歐拉路為4->1->2->1->3

備注:

1≤n≤2×1051≤n≤2×105
1≤ui,vi≤n1≤ui,vi≤n
1≤wi≤1041≤wi≤104

解題報(bào)告：

? ?思維題，不難發(fā)現(xiàn)選擇樹的直徑，剩下的掛到鏈上，這樣一定是最優(yōu)解。

AC代碼：

#include <queue> #include <cstdio> #include <cstring> #include <iostream> #define ll long long using namespace std; const int MAX = 6e5 + 5 ; const int INF = 0x3f3f3f3f; struct Node {int to;int w;int ne; } e[MAX]; struct point {int pos,c;point(){}point(int pos,int c):pos(pos),c(c){}}; int n; int head[MAX]; int cnt = 0 ; bool vis[MAX]; void init() {cnt = 0;memset(head,-1,sizeof(head)); } void add(int u,int v,int w) {e[cnt].to = v;e[cnt].w = w;e[cnt].ne = head[u];head[u] = cnt;cnt++; } int bfs(int x,int &w) {queue <point> q;int maxx = 0;int retp = x ;//返回的點(diǎn)坐標(biāo) memset(vis,0,sizeof(vis) );q.push(point(x,0));vis[x] = 1;point now;while(q.size() ) {point cur = q.front();q.pop();for(int i = head[cur.pos]; i!=-1; i=e[i].ne) {if(vis[e[i].to]) continue;vis[e[i].to] = 1;now.pos = e[i].to;now.c = cur.c + e[i].w;if(now.c>maxx) {maxx = now.c;retp = now.pos;}q.push(now);}//w = maxx;}w = maxx;return retp; } int main() {cin>>n;init();int u,v,w;ll sum = 0;for(int i = 1; i<=n-1; i++) {scanf("%d%d%d",&u,&v,&w);add(u,v,w);add(v,u,w);sum += w;}int ans1 = 0,ans2 = 0;u = bfs(1,ans1);v = bfs(u,ans2);//printf("ans2 = %d\n",ans2);printf("%lld\n",1LL*ans2 + (sum-ans2)*2);return 0 ; } /* 9 1 8 1 1 2 2 2 7 3 2 3 1 3 5 3 3 4 10 4 9 4 5 6 2*/

?

總結(jié)

以上是生活随笔為你收集整理的【牛客 - 369C】小A与欧拉路（bfs树的直径）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。