广州做公司网站的公司有哪些,做公司的网站怎么上线,最好免费观看高清视频直播小说,网络认证入口题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/369/C 来源#xff1a;牛客网
小A给你了一棵树#xff0c;对于这棵树上的每一条边#xff0c;你都可以将它复制任意#xff08;可以为0#xff09;次#xff08;即在这条边连接的两个点之间再…题干
链接https://ac.nowcoder.com/acm/contest/369/C 来源牛客网
小A给你了一棵树对于这棵树上的每一条边你都可以将它复制任意可以为0次即在这条边连接的两个点之间再加一条边权相同的边求所有可能新形成的图中欧拉路的最短长度
欧拉路从图中任意一个点开始到图中任意一个点结束的路径并且图中每条边只通过恰好一次
输入描述:
第一行一个数 n 表示节点个数接下来 n-1 行每行三个整数 u,v,w表示有一条 u 到 v 边权为 w 的无向边
保证数据是一棵树
输出描述:
一行一个整数表示答案
示例1
输入
复制
4
1 2 1
1 3 1
1 4 2
输出
复制
5
说明
一种可能的方案为复制 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
解题报告 思维题不难发现选择树的直径剩下的挂到链上这样一定是最优解。
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 ;//返回的点坐标 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; ie[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.cmaxx) {maxx now.c;retp now.pos;}q.push(now);}//w maxx;}w maxx;return retp;
}
int main()
{cinn;init();int u,v,w;ll sum 0;for(int i 1; in-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*/
