| 179 | long double obj[N],cons[N]; |
| 180 | |
| 181 | int32_t main() { |
| 182 | ll black = 0; |
| 183 | cin >> n >> k; |
| 184 | for(int i = 0; i < n; i++) cin >> a[i], black += a[i]; |
| 185 | for(int i = 1; i < n; i++) { |
| 186 | ll x, y, w; cin >> x >> y >> w; |
| 187 | x--; y--; |
| 188 | g[x].push_back(y); |
| 189 | g[y].push_back(x); |
| 190 | cost[x].push_back(w); |
| 191 | cost[y].push_back(w); |
| 192 | } |
| 193 | for(int i = 0; i < n; i++) dfs(i,-1,0,i); |
| 194 | for(int i = 0; i < n; i++) { |
| 195 | for(int j = 0; j < n; j++) { |
| 196 | if(dis[i][j] <= k )ok[i][j] = 1; |
| 197 | } |
| 198 | } |
| 199 | for(int i = 0; i < n; i++) obj[i] = (long double)1 - a[i]; |
| 200 | lp::init(n,obj,MINIMIZE); |
| 201 | for(int i = 0; i < n; i++)cons[i] = 1.0; |
| 202 | lp::add_constraint(cons,black,EQUAL); |
| 203 | for(int i = 0; i < n; i++) { |
| 204 | for(int j = 0; j < n; j++) { |
| 205 | cons[j] = (long double)ok[i][j]; |
| 206 | } |
| 207 | lp::add_constraint(cons,1.0,GREATEQ); |
| 208 | } |
| 209 | long double ret = lp::solve(); |
| 210 | ll ans = round(ret); |
| 211 | if(ans < 0)ans = -1; |
| 212 | cout<<ans<< '\n'; |
| 213 | return 0; |
| 214 | } |
| 215 | // https://codeforces.com/problemset/problem/375/E |
nothing calls this directly
no test coverage detected