首页 > 其他分享 >AtCoder ABC 259 F Select Edges

AtCoder ABC 259 F Select Edges

时间:2022-08-31 19:12:54浏览次数:77  
标签:AtCoder ch int ABC pb 259 vec 条边 define

题意:

​ 给出一棵树,边带权,对于点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

相关文章

  • [ABC236H] Distinct Multiples
    题目传送门Solution首先不难想到容斥,我们可以钦定若干关系\((u,v)\),表示\(u,v\)的值相同,那么我们不妨设\(g(i)\)表示至少有\(i\)种这种关系的方案数,可以发现答案......
  • AtCoder Beginner Contest 266 G,H
    G考虑先放G和B,此时共有\(C_{G+B}^{B}\)种方案。然后选出\(k\)个G,在前面放上\(R\),共有\(C_{G}^{k}\)种方案。最后我们放剩下的\(R-K\)个R,考虑目前哪些区间内部可以放一段......
  • AtCoder Beginner Contest 266 一句话题解
    AandBsbt,不讲。C垃圾计算几何,问是不是一个凸包,搞份板子交就可以了。D简单dp,令\(f(i,j)\)表示第\(i\)个时间在第\(j\)个位置的最大价值,从上一个时间转移,可以......
  • ABC266 Ex - Snuke Panic (2D)
    ABC266Ex-SnukePanic(2D)挺好的一道题(不过调了好久QAQ方法一比较暴力的做法。首先,你容易想到一个DP状态:\(f(t,x,y)\)表示在\(t\)时刻到达\((x,y)\)的最......
  • ABC265F,G
    ABC265F题解做法byMikukuovo#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintmod=998244353;intn,d;intmain(){ios::sync_wit......
  • AtCoder Beginner Contest 266
    比赛链接:https://atcoder.jp/contests/abc266C-ConvexQuadrilateral题意:平面图上有一个四边形,按照逆时针顺序给定四个点的坐标,判断四边形是不是凸的。思路:求两条......
  • AtCoder Beginner Contest 179
    https://atcoder.jp/contests/abc179我的AC代码https://atcoder.jp/contests/abc179/submissions/me?f.Task=&f.LanguageName=&f.Status=AC&f.User=HinanawiTenshi这......
  • AtCoder Beginner Contest 265(D-E)
    D-IrohaandHaiku(NewABCEdition)题意:找一个最少含有三个点的区间,将区间分成三块,三块的和分别为p,q,r,问是否存在这样的区间题解:先预处理一遍前缀和,和每一个前缀......
  • ABC266.
    D设\(f_{t,p}\)代表在\(t\)时间点时人在\(p\)点的最大收益,在这一步他可以\(p\)增加,不动,\(p\)减少。于是得出状态转移方程:\(f_{t,p}=\max(f_{t-1,p-1},f_{t-1,......
  • ABC266 做题笔记
    AProblem给定一个字符串,输出正中间那个字符。link->https://atcoder.jp/contests/abc266/tasks/abc266_a。Solution简单题。Code点击查看代码#include<bits/stdc+......