1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
| #include <iostream> #include <cstdio> #include <cstring> using namespace std; #define N 110 #define INF 100000000000LL #define LL long long #define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
int n,tot,head[N],val[N],sum,ave,num; int cnt[N],totval[N],up[N]; struct edge{ int u,v,w,next; edge(){} edge(int __u,int __v,int __w){ u = __u; v = __v; w = __w; } }e[2*N]; LL dp[N][N];
inline int Abs(int x){ return x > 0 ? x : -x; }
inline void add(int u,int v,int w){ e[tot] = edge(u,v,w); e[tot].next = head[u]; head[u] = tot++; }
void updata(int u,int fa){ int cap = min(cnt[u],num); LL tmp[N]; fill(tmp,tmp+n,INF); tmp[0] = 0; for(int k = head[u]; k != -1; k = e[k].next){ int v = e[k].v; int w = e[k].w; if(v == fa) continue; for(int j = cap; j >= 0; j--){ LL res = INF; for(int k = 0; k <= j && k <= cnt[v]; k++) if(tmp[j-k] != INF && dp[v][k] != INF) res = min(res , tmp[j-k]+dp[v][k]); tmp[j] = res; } } for(int i = 0; i <= cap; i++){ LL cost = up[u] * Abs(ave * cnt[u] + i - totval[u]); if(i == 0) dp[u][0] = tmp[0] + cost; else dp[u][i] = min(tmp[i-1] , tmp[i]) + cost; } }
void dfs(int u,int fa,int weigth){ bool leaf = true; cnt[u] = 1; up[u] = weigth; totval[u] = val[u]; for(int k = head[u]; k != -1; k = e[k].next){ int v = e[k].v; int w = e[k].w; if(v == fa) continue; leaf = false; dfs(v,u,w); cnt[u] += cnt[v]; totval[u] += totval[v]; } if(leaf){ int cost; cost = up[u] * Abs(ave*cnt[u]-totval[u]); dp[u][0] = cost; cost = up[u] * Abs(ave*cnt[u]+1-totval[u]); dp[u][1] = cost; return; } updata(u,fa); }
int main(){ while(scanf("%d",&n)!=EOF){ tot = sum = 0; cl(head,-1); for(int i = 0; i < n; i++){ scanf("%d",&val[i]); sum += val[i]; } for(int i = 1; i < n; i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } ave = sum / n; num = sum % n; fill(dp[0],dp[n],INF); dfs(0,-1,0); printf("%lld\n",dp[0][num]); } return 0; }
|