题意:
给出一棵树,边带权,对于点i,最多保留d[i]条边,可以被分成连通块,请问边权和最大是多少
分析:
因为可以被分成连通块,我们就可以对点i划分两种状态。第一种是点i不与父亲节点相连,那么他最多连接d[i] - 1条边;第二种是点i与父亲节点相连,那么他最多连接d[i]条边。
实现:
我们可以用\(f[i][0 / 1]\)表示以i为根节点的子树,且节点i连接\((d[i] - 1) / d[i]\)条边的最大权值和
自然答案就是\(f[1][1]\)。
对于节点\(u\),遍历他的儿子\(v\),连接那些\(f[v][0] + w > f[v][1]\)的儿子\(v\),意思是连接u的收益比他自己连边的收益更高,因为有\(d[u]\)条边的限制,把这些待加入的儿子放到一个set(sort)里优先取最大值。
总结:
这种先加一种解,再判断是否补上差值的做法是贪心的常见实现方式。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cout << x << endl;
#define SZ(x) (int)x.size()
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, LL> PII;
const int inf = 0x3f3f3f3f;
void read(int &x) {int s = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) {f = (ch == '-' ? -1 : f); ch = getchar();} while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();} x = s * f;}
const int N = 300005;
int n;
vector<PII> g[N];
int d[N];
LL f[N][2]; //以i为根的子树,且边数小于d[i] / 小于等于d[i]
void dfs(int u, int fa)
{
vector<LL> vec;
for(PII e : g[u])
{
int v = e.first, w = e.second;
if(v == fa) continue;
dfs(v, u);
vec.pb(f[v][0] + w - f[v][1]);
f[u][0] += f[v][1], f[u][1] += f[v][1];
}
sort(all(vec));
reverse(all(vec)); //贪心大到小
for(int i = 0; i < SZ(vec); i ++)
{
if(vec[i] <= 0) break; //后面的不要了
if(i < d[u] - 1) f[u][0] += vec[i]; //加入的边不超过d[u] - 1
if(i < d[u]) f[u][1] += vec[i];
}
if(!d[u]) f[u][0] = -2e18; //这条边不能被连接,负无穷
}
signed main()
{
cin >> n;
rep(i, 1, n + 1) cin >> d[i];
rep(i, 1, n)
{
int u, v;
LL c;
cin >> u >> v >> c;
g[u].pb({v, c}); g[v].pb({u, c});
}
dfs(1, -1);
cout << f[1][1] << '\n';
}
标签:AtCoder,ch,int,ABC,pb,259,vec,条边,define
From: https://www.cnblogs.com/DM11/p/16644240.html