Codeforces Round #646 (Div. 2) E（贪心，bfs）

Codeforces Round #646 (Div. 2) E

题目大意： 给一棵树，每个节点有三个权值 A,B,C, (B,C为0或1)，每次你可以花费 A[u] *k的代价让A子树中的任意 k 个节点交换彼此的 B ，问让所有节点的 B=C 至少花费多少代价。

思路： b[i]=1时 代表1 0，b[i]=-1代表0 1， 等于0就是相同的，不需要交换。然后bfs，从下往上（从上往下递归）开始计算，b[i]就代表这颗树还又多少个不能被交换的。

代码：

#include<bits/stdc++.h> using namespace std;#define LL long long LL ans; int x, y, n, a[200005], b[200005]; vector<int> g[200005];void dfs(int v, int par) {int tot = abs(b[v]);for(int u : g[v]) {if(u == par) continue;a[u] = min(a[v], a[u]);dfs(u, v); b[v] += b[u];tot += abs(b[u]);}ans += 1LL * (tot - abs(b[v])) * a[v]; }int main() {ios::sync_with_stdio(0);cin.tie(0);cin >> n;for(int i=1;i<=n;i++) {cin >> a[i] >> x >> y;b[i] = x - y;}while(--n) {cin >> x >> y;g[x].push_back(y);g[y].push_back(x);}dfs(1, 0);cout << (b[1] ? -1 : ans); }

总结

以上是生活随笔为你收集整理的Codeforces Round #646 (Div. 2) E（贪心，bfs）的全部内容，希望文章能够帮你解决所遇到的问题。

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