EOJ - 3631 Delivery Service 2018.8华师大月赛(树链剖分+贪心)-白红宇的个人博客

EOJ - 3631 Delivery Service 2018.8华师大月赛(树链剖分+贪心)

发布日期：2021-08-13 06:10:19 浏览次数：1 分类：技术文章

本文共 2472 字，大约阅读时间需要 8 分钟。

链接：https://acm.ecnu.edu.cn/contest/103/problem/D/

题意：给你一棵无向边连接的树，边的权值可以任意互换。有m次运输，每次的花费是点u到v路径上边的权值和。

必须在全部运输开始前安排好边的权值，求m次运输总的最小花费。

分析：肯定是边被覆盖次数越多的边优先得到较小的权值。轻重链剖分之后，用线段树或树状数组维护每点的覆盖次数。最后对边和权值排序后贪心选取即可。

#include
     
      #include
      
       #include
       
        #include
        
         #define lson rt<<1#define rson rt<<1|1#define Lson l,m,lson#define Rson m+1,r,rsontypedef long long LL;using namespace std;const int maxn =2e5+5;struct Edge{    int to,next;}E[2*maxn];int n,head[maxn],tot;int cnt,idx,size[maxn],fa[maxn],son[maxn],dep[maxn],top[maxn],id[maxn],rnk[maxn];int e[maxn][2];int W[maxn];struct Node{    int sum,add;}tree[maxn<<2];void init(){       cnt=idx=tot=0;    memset(head,-1,sizeof(head));    dep[1]=0,fa[1]=1,size[0]=0;    memset(son,0,sizeof(son));}void AddEdge(int u,int v){    E[tot] = (Edge){v,head[u]};    head[u]=tot++;}void dfs1(int u){    size[u]=1;    for(int i=head[u];~i;i=E[i].next){        int v=E[i].to;        if(v!=fa[u]){            fa[v]=u;            dep[v]=dep[u]+1;            dfs1(v);            size[u]+=size[v];            if(size[son[u]]
         
          >1;        tree[lson].sum += (m-l+1)*tree[rt].add;        tree[rson].sum += (r-m)*tree[rt].add;         tree[rt].add =0;    }}void build(int l,int r,int rt){    tree[rt].add = 0;    if(l==r){        tree[rt].sum = 0;        return;    }    int m = (l+r)>>1;    build(Lson);    build(Rson);    pushup(rt);}void update(int L,int R,int v,int l=1,int r=n,int rt=1){    if(L<=l && R>=r){        tree[rt].sum +=(r-l+1)*v;        tree[rt].add +=v;        return ;    }    pushdown(l,r,rt);    int m =(l+r)>>1;    if(L<=m) update(L,R,v,Lson);    if(R>m) update(L,R,v,Rson);    pushup(rt);}int query(int p,int l=1,int r=n,int rt=1){        //单点    if(l==r) return tree[rt].sum;    pushdown(l,r,rt);    int m = (l+r)>>1,ans=0;    if(p<=m) ans= query(p,Lson);    else ans =query(p,Rson);    pushup(rt);    return ans;}void UPDATE(int u,int v,int w=1){    while(top[u]!=top[v]){        if(dep[top[u]]
          
           dep[v])swap(u,v); update(id[son[u]],id[v],w);}int vis[maxn];int main(){ #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int m,q,u,v; char op[5]; while(scanf("%d",&n)==1){ init(); for(int i=1;i
           
            dep[e[i][1]]) swap(e[i][0],e[i][1]); } scanf("%d",&q); while(q--){ scanf("%d%d",&u,&v); UPDATE(u,v); } sort(W+1,W+n); LL res=0; for(int i=1;i

转载于:https://www.cnblogs.com/xiuwenli/p/9495788.html

转载地址：https://blog.csdn.net/weixin_30677617/article/details/96598644 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：python 内置函数(二)

下一篇：Java异常处理

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章