C - 哗啦啦村的扩建
Time Limit: 2000/1000MS (Java/Others) Memory Limit: 512000/256000KB (Java/Others)
Problem Description
呀呀呀，哗啦啦村在日渐发展中，越来越大了。
唐老师看到这欣欣向荣的情景，感到非常开心。
狗哥在旁边，“喏，我们村子扩建这么快，肯定用了不少钱吧？”
唐老师说：“是呀，不过这些钱都不及我零花钱的万万分之一。”
那么这时候问题来了，唐老师的零花钱至少应该有多少钱呢？
狗哥也想知道这道题的答案，于是他拜托了青君同学，了解到了村子扩建的费用。
啊，原来村子的扩建费用，就是修建道路的费用。
整个村子可以看作有n个房子，村子会修建n-1条道路，保证从任意房子可以到达任意其他房子。
那修建这n-1条道路的费用怎么记呢？对于每条道路，假设这条道路左边有x个房子，右边有y个房子，这条道路长度为k，那么费用就是k*|x-y|。
那么唐老师的零花钱至少有多少钱呢？现在你应该知道了吧。
Input
第一行一个整数，表示这个村子有n个房子
接下来n-1行，表示每条道路的信息，三个整数 a,b,c，表示a,b之间有一条道路，这条路的长度为c
1<=n<=50,000
1≤ai, bi≤n
0 ≤ci≤ 10^6
Output
输出一个整数，表示唐老师的零花钱至少有多少钱
Sample Input
61 2 11 3 11 4 26 3 15 2 1
Sample Output
2000000000 题目大意： 输入N，表示有N个点，然后下面有N-1条边，（这些边能够构成树，不会出现环或者孤立点，题目限定的），每一条边上有权值k，要求这条边的费用，则 设这条边左边的点数为x，右边的点数为y，这条边的费用=k*|x-y|，统计全部边的费用即可。输出费用，如果非0，在加上00000000，否则输出0. 解法： 用邻接表来保存这一无向图，然后，从这无向图的任意某一点，去他的查找子节点，用Count[i]统计以点i为节点所包含点的个数。 依次更新每一条边上的值，然后累加即可。详情请见代码：
1 #include2 #include 3 #include 4 #include 5 #define MAX 50010 /*点数*/ 6 typedef long long LL; 7 using namespace std; 8 LL Sum_Num; 9 int Len; 10 int Point[MAX]; 11 int Count[MAX]; 12 int First[MAX]; /*First[x]：x表示头结点为x，First[x]表示下一条边的编号*/ 13 struct edge 14 { 15 int TO; /*下一个顶点*/ 16 int Next; /*记录下一条边的编号*/ 17 LL Vlaue; /*权值*/ 18 }ID[3*MAX]; /*边表,无向图的边数记得多弄些*/ 19 20 int SIGN;/*链表的边数，链表的边数=无向图边数*2=有向图边数,初始化为1*/ 21 22 void Add_E(int x,int y,int z) /*添加边*/ 23 { 24 ID[SIGN].TO=y; 25 ID[SIGN].Vlaue=z; 26 ID[SIGN].Next=First[x]; 27 First[x]=SIGN++; 28 } 29 30 int ABS(int Num) 31 { 32 if(Num>=0)return Num; 33 else return -Num; 34 } 35 void DFS(int x) 36 { 37 int i; 38 Point[x]=0; 39 for(i=First[x];i!=0;i=ID[i].Next) 40 { 41 if(Point[ID[i].TO]==0)continue; 42 else 43 { 44 DFS(ID[i].TO); 45 Count[x]+=Count[ID[i].TO];/*更新点数*/ 46 47 ID[i].Vlaue=ID[i].Vlaue*ABS(Len-2*Count[ID[i].TO]); 48 /*printf("(%d-%d):%d\n",x,ID[i].TO,ID[i].Vlaue);*/ 49 Sum_Num+=ID[i].Vlaue;/*更新费用,累加费用*/ 50 } 51 } 52 } 53 void Deal() 54 { 55 int i,j,k; 56 Sum_Num=0; 57 DFS(1);/*可从任意点出发*/ 58 if(Sum_Num!=0) 59 printf("%lld00000000\n",Sum_Num); 60 else printf("0\n"); 61 62 } 63 64 int main() 65 { 66 int N,M; 67 int x,y,z,i; 68 while(scanf("%d",&N)!=EOF) 69 { 70 SIGN=1;M=N-1;Len=N; 71 for(i=1;i<=N;i++)/*初始化*/ 72 {First[i]=0;Point[i]=1;Count[i]=1;} 73 for(i=1;i<=M;i++) 74 { 75 scanf("%d %d %d",&x,&y,&z); 76 Add_E(x,y,z); 77 Add_E(y,x,z); 78 } 79 Deal(); 80 } 81 return 0; 82 } 83 84 /* 85 6 86 1 2 1 87 1 3 1 88 1 4 2 89 6 3 1 90 5 2 1 91 92 8 93 1 2 1 94 2 3 1 95 3 5 1 96 3 6 1 97 2 4 1 98 4 7 1 99 4 8 1100 101 */