hdu4118

题意:
      给你一颗无向带权树,每个定点上有一个人,问所有定点都不在自己位置上的最长路径总和是多少..

  思路:
      其实很简单,贪心的想下,既然要求全局最大,那么对于每一条边用的次数越多越好,

对于每一条边 ans +=  他的权值*min(他左边点的个数,有边点的个数)//为了保证每一个都在边的另一面找到位置,最后输出ans * 2,因为是双向的,a ->b 那么 b ->a ,还有一个就是爆栈,杭电上好像是递归多少次后就默认是你无限递归了,所以加上防止爆栈的那句就行了...

#pragma comment(linker, "/STACK:1024000000,1024000000") #include<stdio.h> #include<string.h>#define N_edge 200000 + 100 #define N_node 100000 + 100 typedef struct {int from ,to ,next;__int64 cost; }STAR;STAR E[N_edge]; int list[N_node] ,tot; __int64 ge[N_node];void add(int a ,int b ,__int64 c) {E[++tot].from = a;E[tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot; }__int64 minn(__int64 a ,__int64 b) {return a < b ? a : b; }__int64 DFS(int s ,int fa) {__int64 sum = 0;for(int k = list[s] ;k ;k = E[k].next){ int to = E[k].to; if(to == fa) continue;sum += DFS(to ,s);}ge[s] = sum;return sum + 1; }int main () {int n ,i ,a ,b ,t ,cas = 1;__int64 c;scanf("%d" ,&t);while(t--){scanf("%d" ,&n);memset(list ,0 ,sizeof(list));tot = 0;for(i = 1 ;i <= n - 1 ;i ++){scanf("%d %d %I64d" ,&a ,&b ,&c);add(a ,b ,c);add(b ,a ,c);}memset(ge ,0 ,sizeof(ge));DFS(1 ,-1);__int64 sum = 0;for(i = 1 ;i <= tot ;i += 2){a = E[i].from;b = E[i].to;c = E[i].cost;if(ge[a] < ge[b]){a = a + b;b = a - b;a = a - b;}sum += minn(ge[b] + 1 ,n - ge[b] - 1) * c;}printf("Case #%d: %I64d\n" ,cas ++ ,sum * 2);}return 0; }

总结

以上是生活随笔为你收集整理的hdu4118的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。

网址：hdu4118 https://www.yuejiaxmz.com/news/view/1250056

随便看看