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）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。