ACdream 1103 瑶瑶正式成为CEO （树链剖分+最小费用最大流）

落日映苍穹つ 2022-06-12 01:15 164阅读 0赞

\_题目链接：  
[ACdream 1103][]

题意：中文题面….

题解：  
因为 C  修改操作要在树上修改边权，我们用树链剖分去解决就好了。  
然后对于 Q  查询操作，我们可以用最小费用最大流去求最小费用就可以了。

建图问题：  
假设每条边都跑了 0  的流量，我们先算出跑了 0  的流量的费用sum=∑c i  ，然后对于一条边，当跑了小于 a i   的流量的时候，每次增加一点流量，就相当于减小了 c i   的费用，所以可以把一条边拆成两条边，一条是上界为 a i   ，费用为 d i −c i   的边，另一条是上界为无穷，费用为 b i \+d i   的边。然后跑网络流就可以了。  
跑完最小费用最大流后\+sum 就是答案。即代码中的：sum\+G.MCMF(n\+1,u).   
加了读入挂快100ms 左右.

AC代码：

/*
    * this code is made by LzyRapx
    * Problem: 1103
    * Verdict: Accepted
    * Submission Date: 2017-07-11 19:11:24
    * Time: 652MS
    * Memory: 2504KB
    */
    #include<stdio.h>
    #include<iostream>
    #include<queue>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    typedef long long ll;
    #define lson rt<<1
    #define rson rt<<1 | 1
    const int INF = 0x3f3f3f3f;
    const int maxn = 510;
    const int maxm = 4*(1000+2000+12);
    int read(){ int v = 0, f = 1;char c =getchar();
    while( c < 48 || 57 < c ){
       if(c=='-') f = -1;c = getchar();}
    while(48 <= c && c <= 57) v = v*10+c-48, c = getchar();
    return v*f;}
    struct MinCostMaxFlow{
        int head[maxn],pnt[maxm],cap[maxm];
        int flow[maxm],nxt[maxm],ecnt;
        ll cost[maxm];
        void init()
        {
            memset(head,-1,sizeof(head));
            ecnt = 0;
        }
        inline void addedge(int u,int v,int cp,ll co)
        {
            pnt[ecnt] = v; cap[ecnt] = cp;  cost[ecnt] = co;
            nxt[ecnt] = head[u]; head[u] = ecnt++;
    
            pnt[ecnt] = u; cap[ecnt] = 0;  cost[ecnt] = -co;
            nxt[ecnt] = head[v]; head[v] = ecnt++;
        }
        inline void clear()
        {
            memset(flow,0,sizeof(flow));
        }
        int pre[maxn],dis[maxn];
        bool vis[maxn];
        bool spfa(int s,int t)
        {
            memset(dis,INF,sizeof(dis));
            queue<int>que;
            que.push(s);
            dis[s] = 0;
            while(!que.empty())
            {
                int u =  que.front();
                que.pop();
                vis[u] = false;
                for(int i=head[u]; ~i; i=nxt[i])
                {
                    int v = pnt[i];
                    if(cap[i] > flow[i] && dis[v] > dis[u] + cost[i])
                    {
                        dis[v] = dis[u] + cost[i];
                        pre[v] = i;
                        if(!vis[v])
                        {
                            vis[v] = true;
                            que.push(v);
                        }
                    }
                }
            }
            return dis[t]!=INF;
        }
        ll MCMF(int s,int t)
        {
            ll Mincost = 0;
            while(spfa(s,t))
            {
                int ang = INF;
                for(int u = t; u != s; u = pnt[pre[u]^1])
                {
                    ang = min(ang, cap[ pre[u] ] - flow[pre[u]]);
                }
                for(int u = t; u != s; u = pnt[pre[u]^1])
                {
                    flow[pre[u]] += ang;
                    flow[pre[u]^1] += ang;
                }
                Mincost += 1LL*dis[t] * ang;
            }
            return Mincost;
        }
    }G;
    
    struct Edge{
        int u,v,a,b,c,d;
        void Read()
        {
            //scanf("%d%d%d%d%d%d",&u,&v,&a,&b,&c,&d);  
            u=read(),v=read(),a=read(),b=read(),c=read(),d=read();
        }
    }tree[maxn],edge[maxm];
    
    int idx[maxm],pre[maxm],eid[maxm];
    struct Solve{
        int n,m;
        int head[maxn],pnt[maxn*2],nxt[maxn*2],ecnt;
        int Hash[maxm];
        int dep[maxn],size[maxn],son[maxn],fa[maxn],top[maxn],SegId[maxn],tot;
        void init(){
            memset(head, -1, sizeof(head));
            ecnt = tot = 0;
        }
        inline void addedge(int u,int v,int i){
            pnt[ecnt] = v; idx[ecnt] = i; nxt[ecnt] = head[u]; head[u] = ecnt++;
            pnt[ecnt] = u; idx[ecnt] = i; nxt[ecnt] = head[v]; head[v] = ecnt++;
        } 
        struct Segment{
            struct node{
                int l,r,add;
                node(){};
                node(int l,int r,int add):l(l),r(r),add(add){}
            }p[maxn<<2];
    
            void build(int rt,int l,int r)
            {
                p[rt] = node(l,r,0);
                if(l==r)return ;
                int mid = (l + r)>>1;
                build(lson,l,mid);
                build(rson,mid+1,r);
            }
            void push_down(int rt)
            {
                if(p[rt].add != 0){
                    p[lson].add += p[rt].add;
                    p[rson].add += p[rt].add;
                    p[rt].add = 0;
                }
            }
            void update(int rt,int l,int r,int val)
            {
                if(l <= p[rt].l && p[rt].r <= r){
                    p[rt].add += val;
                    return;
                }
                int mid =(p[rt].l + p[rt].r)>>1;
                if(l<=mid)update(lson,l,r,val);
                if(r>mid)update(rson,l,r,val);
            }
            void push_up(int rt)
            {
                if(p[rt].l==p[rt].r)
                {
                    if(p[rt].l > 1)
                    {
                        tree[ eid[ p[rt].l ] ].a += p[rt].add;
                    }
                    p[rt].add = 0;
                    return ;
                }
                push_down(rt);
                push_up(lson);
                push_up(rson);
            }
        }ST;
        void dfs_first(int u,int f,int depth)
        {
            fa[u] = f, size[u] = 1, son[u] = -1, dep[u] = depth;
            int maxSize = 0;
            for(int i = head[u]; ~i; i = nxt[i])
            {
                int v = pnt[i];
    
                if(v == f)continue;
    
                pre[v] = i;
    
                dfs_first(v,u,depth + 1);
                size[u] += size[v];
                if(size[v] > maxSize)
                {
                    maxSize = size[v],son[u] = v;
                }
            }
        }
        void dfs_second(int u,int header)
        {
            SegId[u] = ++tot, top[u] = header,eid[tot] = idx[pre[u]];
            if(son[u] == -1)return;
            if(son[u] != -1){
                dfs_second(son[u],header);
            }
            for(int i = head[u]; ~i ;i = nxt[i])
            {
                if(pnt[i] != fa[u] && pnt[i] != son[u])
                {
                    dfs_second(pnt[i],pnt[i]);
                }
            }
        }
        inline void InitG()
        {
            G.init();
            for(int i = 1;i < n;i++)
            {
                Hash[i] = G.ecnt;
                Edge& e = tree[i];
                G.addedge(e.u, e.v, max(e.a , 0), e.d - e.c);
                G.addedge(e.u, e.v, INF, e.d + e.b);
            } 
            for(int i = 1;i <= m;i++)
            {
                Edge& e = edge[i];
                G.addedge(e.u, e.v, max(e.a , 0), e.d - e.c);
                G.addedge(e.u, e.v, INF, e.d + e.b);
            } 
            G.addedge(n + 1, 1, 0,0);
        }
        ll query(int u,int val)
        {
            ST.push_up(1);
            ll sum = 0;
    
            for(int i = 1;i < n;i++){
    
                G.cap[ Hash[i] ] = max(0,tree[i].a);
    
                sum += (ll)max(0,tree[i].a) * (ll)tree[i].c;
            }
    
            for(int i=1;i <= m;i++)
            {
                sum += (ll)max(0,edge[i].a) * (ll)edge[i].c;    
            }
            G.cap[G.ecnt - 2] = val;
            G.clear();
            return sum + G.MCMF(n + 1,u); 
        }
        void modify(int u,int v,int val)
        {
            int p = top[u], q = top[v];
            while(p!=q)
            {
                if(dep[p] < dep[q])
                {
                    swap(p,q);
                    swap(u,v);
                }
                ST.update(1,SegId[p],SegId[u],val);
                u = fa[p];
                p = top[u];
            }
    
            if(u != v)
            {
                if(dep[u] < dep[v]){
                    swap(u,v);
                }
                ST.update(1, SegId[v] + 1, SegId[u],val);
            }
        }
        inline void work()
        {
            //scanf("%d%d",&n,&m);
            n=read(),m=read();
    
            init();
            /*tree*/
            for(int i = 1;i < n;i++){
                tree[i].Read();
                addedge(tree[i].u, tree[i].v, i);
            }
            for(int i = 1; i <= m;i++)
            {
                edge[i].Read();
            }
            /*----*/
            InitG();
    
            ST.build(1,1,n);
            dfs_first(1,-1,0);
            dfs_second(1,1);
    
        //  cout<<"finish"<<endl;
    
            int Q;
        //  scanf("%d",&Q);
            Q=read();
            int a,b,c;
            while(Q--)
            {
                char op[5];
                scanf("%s",op);
                if(op[0]=='Q')
                {
                    //scanf("%d%d",&a,&b);
                    a=read(),b=read();
                //  cout<<"scanf finish"<<endl;     
                    printf("%lld\n",query(a,b));
                }
                else if(op[0]=='C')
                {
                    //scanf("%d%d%d",&a,&b,&c);
                    a=read(),b=read(),c=read();
                    modify(a,b,c);
                }
            }
        }
    }gao;
    
    int main()
    {
        gao.work();
    
        return 0;
     }

[ACdream 1103]: http://acdream.info/problem?pid=1103