牛客练习赛56 B 小琛和他的学校

题目链接：https://ac.nowcoder.com/acm/contest/3566/B

思路：一条路可把图分为左右两部分。

l_ci, l_peo, r_ci, r_peo, w 分别为左边城市数和人数，右边城市数和人数，该路的费用。

我们知道，左边的人要去右边的r_ci个城市，右边的人要去左边的l_ci个城市，

那么该路的费用就是 cost = 2*w*(l_ci*r_peo + r_ci*l_peo);（注意来回）。

我们可以用拓扑排序来得出一条边的左右人数和城市情况。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <queue>
 5 using namespace std;
 6 typedef long long ll;
 7 
 8 const int N = (int)2e5+100;
 9 struct node{
10     int to,nxt;
11 }e[N<<1];
12 struct Info{
13     int ci,peo;
14     Info(){ci = peo = 0;}
15 }info[N];
16 int A[N],W[N],du[N],head[N];//人数，路费,度数
17 bool vis[N];
18 int n,u,v,w,tot;ll sum_peo;
19 
20 inline void add(int u,int v){
21     e[tot].to = v; e[tot].nxt = head[u]; head[u] = tot++;
22     e[tot].to = u; e[tot].nxt = head[v]; head[v] = tot++;
23 }
24 
25 void top_sort(){
26     //度数为1的压入
27     queue<int > que;
28     for(int i = 1; i <= n; ++i){
29         if(du[i] == 1){
30             vis[i] = 1;
31             que.push(i);
32         }
33     }
34 
35     while(!que.empty()){
36         int now = que.front(); que.pop();
37         //加上自己城市的情况
38         info[now].ci += 1;
39         info[now].peo += A[now];
40         for(int o = head[now]; ~o; o = e[o].nxt){
41             int to = e[o].to;
42             if(!vis[to]){
43                 //传递自己城市的情况
44                 info[to].ci += info[now].ci;
45                 info[to].peo += info[now].peo;
46                 if(--du[to] == 1){
47                     vis[to] = 1;
48                     que.push(to);
49                 }
50             }
51         }
52     }
53 }
54 
55 void show_info(){
56     for(int i = 1;i <= n; ++i){
57         printf("now = %d city = %d people = %d
",i,info[i].ci,info[i].peo);
58     }
59 }
60 
61 inline ll cost(Info& u,int i){
62     Info v;
63     v.ci = n-u.ci;
64     v.peo = sum_peo - u.peo;
65   //  printf("u.c = %d v.c = %d  u.p = %d v.p = %d W = %d
",u.ci,v.ci,u.peo,v.peo,W[i]);
66     return (ll)2*W[i]*((ll)u.ci*v.peo+(ll)v.ci*u.peo);
67 }
68 
69 int main(){
70 
71     scanf("%d",&n);
72     for(int i = 0; i <= n; ++i) head[i] = -1; tot = 0;
73     for(int i = 1; i <= n; ++i){
74         scanf("%d",A+i);
75         sum_peo += A[i];
76     }
77     for(int i = 1; i < n; ++i){
78         scanf("%d%d%d",&u,&v,W+i);
79         add(u,v);
80         ++du[u]; ++du[v];//无向边
81     }
82     top_sort();
83     //show_info();
84     for(int i = 0; i < 2*(n-1); i+=2){
85         //我们总是选一条边城市数少的一边去得出另一边的人数和城市情况
86         int x = info[e[i].to].ci < info[e[i^1].to].ci ? e[i].to : e[i^1].to;
87      //   printf("city = %d
",x);
88         printf("%lld
",cost(info[x],1+(i>>1)));
89     }
90 
91     return 0;
92 }