[ZJOI2010]网络扩容

题目

[ZJOI2010]网络扩容
\(A：\)报告，发现一道水题
\(B：\)切掉切掉

做法

考虑做第二问，\(u\frac{~~f~~}{~~0~~}v,u\frac{~~K~~}{~~c~~}v\)，然后跑最大流最小费用就好了

My complete code

#include<bits/stdc++.h>
using namespace std;
typedef int LL;
const LL maxn=30009,inf=0x3f3f3f3f;
LL n,m,S,T,K,ans;
LL U[maxn],V[maxn],F[maxn],W[maxn];
struct E{
    struct node{
        LL to,next,f,c;
    }dis[maxn];
    LL num;
    LL head[maxn],lev[maxn];
    bool visit[maxn];
    inline void Init(){
        memset(head,-1,sizeof(head)), num=-1;
    }
    
    inline void Add(LL u,LL v,LL f,LL c=0){
        dis[++num]=(node){v,head[u],f,c}, head[u]=num;
    }
    inline bool Bfs(){
        queue<LL> que; 
        memset(lev,0,sizeof(lev)), memset(visit,false,sizeof(visit));
        que.push(S); visit[S]=true; lev[S]=0;
        while(que.size()){
            LL u(que.front()); que.pop();
            for(LL i=head[u];~i;i=dis[i].next){
                LL v(dis[i].to);
                if(!visit[v] && dis[i].f)
                    lev[v]=lev[u]+1,visit[v]=true,que.push(v);
            }
        }return lev[T];
    }
    LL Dfs(LL u,LL f){
        if(u==T) return f;
        LL tmp(f);
        for(LL i=head[u];~i;i=dis[i].next){
            LL v(dis[i].to),now;
            if(dis[i].f &&lev[v]==lev[u]+1){
                if(now=Dfs(v,min(tmp,dis[i].f))){
                    dis[i].f-=now, dis[i^1].f+=now;
                    tmp-=now;
                    if(!tmp) break;
                }else lev[v]=-1;
            }
        }return f-tmp;
    }
    inline LL Dinic(){
        LL ret(0);
        while(Bfs()) ret+=Dfs(S,inf);
        return ret;
    }
    
    
    LL pre_d[maxn],pre_v[maxn],cost[maxn],flow[maxn];
    inline bool EK(){
        memset(pre_d,0,sizeof(pre_d)), memset(pre_v,0,sizeof(pre_v)), memset(cost,inf,sizeof(cost));
        memset(flow,0,sizeof(flow));
        queue<LL> que;
        que.push(S);
        cost[S]=0, flow[S]=inf;
        while(que.size()){
            LL u(que.front()); que.pop();
            for(LL i=head[u];~i;i=dis[i].next){
                LL v(dis[i].to);
                if(cost[v]>cost[u]+dis[i].c && dis[i].f){
                    flow[v]=min(flow[u],dis[i].f);
                    cost[v]=cost[u]+dis[i].c;
                    pre_d[v]=i, pre_v[v]=u;
                    que.push(v);
                }
            }
        }return pre_v[T];
    }
    inline LL Solve(){
        LL ret(0);
        while(EK()){
            ret+=flow[T]*cost[T];
            for(LL i=T;i!=S;i=pre_v[i]){
                dis[pre_d[i]].f-=flow[T],
                dis[pre_d[i]^1].f+=flow[T];
            }
        }return ret;
    }
}G1,G2;
int main(){
    cin>>n>>m>>K;
    G1.Init();
    S=1, T=n;
    for(LL i=1;i<=m;++i)
        cin>>U[i]>>V[i]>>F[i]>>W[i],
        G1.Add(U[i],V[i],F[i]), G1.Add(V[i],U[i],0);
    ans=G1.Dinic();
    printf("%d ",ans);
    
    G2.Init();
    S=n+1,T=n+2;
    G2.Add(S,1,ans+K,0),G2.Add(1,S,0,0);
    G2.Add(n,T,ans+K,0),G2.Add(T,n,0,0);
    for(LL i=1;i<=m;++i){
        G2.Add(U[i],V[i],F[i],0), G2.Add(V[i],U[i],0,0);
        G2.Add(U[i],V[i],K,W[i]), G2.Add(V[i],U[i],0,-W[i]);
    }
    ans=G2.Solve();
    printf("%d",ans);
    return 0;
}

[ZJOI2010]网络扩容

原文：https://www.cnblogs.com/y2823774827y/p/10423103.html