CF708D Incorrect Flow

有源汇上下界最小费用可行流。（= =）

对每条给定的边连边：

首先\(f_i\)是给定的，所以要有一条这个边而且要流满，先\(a_i-b_i\)连一条上下界为\([f_i,f_i]\)的边

如果\(f_i\leq c_i\)，可以增加流量或者减少流量，如果减少只要减流量就可以了，如果增加，在\([f_i,c_i]\)这一段只要加流量，大于\(c_i\)就要流量和容量都加，整合一下，减少就是连反向边，\((b_i,a_i,f_i,1)\)；增加有两段，费用是递增的，\((a_i,b_i,c_i-f_i,1),(a_i,b_i,inf,2)\)

如果\(f_i\geq c_i\)，首先钦定把\(c_i\)加到\(f_i\)，答案先加上\(f_i-c_i\)那么再增加流量就要流量和容量都加，连边\((a_i,b_i,inf,2)\)；如果要减的话，可以发现最后的流量如果在\([c_i,f_i]\)这个范围内，修改量都是\(f_i-c_i\)的，这个已经加过了就不用管了，就是连\((b_i,a_i,f_i-c_i,0)\)；继续减就要减流量了，连\((b_i,a_i,c_i,1)\)。

就做完了。

#include<bits/stdc++.h>

#define il inline

#define vd void

typedef long long ll;

il int gi(){

    int x=0,f=1;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

int fir[110],dis[1010],nxt[1010],w[1010],cost[1010],id=1,S,T;

il vd link(int a,int b,int c,int d){

    nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c,cost[id]=d;

    nxt[++id]=fir[b],fir[b]=id,dis[id]=a,w[id]=0,cost[id]=-d;

}

il bool Mincost(ll&totalcost){

    static int que[110],hd,tl,lst[110];

    static ll dist[110];

    static bool inq[110];

    hd=tl=0;que[tl++]=S;inq[S]=1;

    for(int i=1;i<=T;++i)dist[i]=1e9;

    dist[S]=0;

    while(hd^tl){

        int x=que[hd];

        for(int i=fir[x];i;i=nxt[i])

            if(w[i]&&dist[dis[i]]>dist[x]+cost[i]){

                dist[dis[i]]=dist[x]+cost[i],lst[dis[i]]=i;

                if(!inq[dis[i]]){

                    inq[dis[i]]=1,que[tl++]=dis[i];

                    if(tl==110)tl=0;

                }

            }

        inq[x]=0,++hd;

        if(hd==110)hd=0;

    }

    if(dist[T]>0)return 0;

    int flow=1e9;

    for(int i=lst[T];i;i=lst[dis[i^1]])flow=std::min(flow,w[i]);

    for(int i=lst[T];i;i=lst[dis[i^1]])totalcost+=1ll*flow*cost[i],w[i]-=flow,w[i^1]+=flow;

    return 1;

}

int main(){

    int n=gi(),m=gi(),a,b,c,f;S=n+1,T=n+2;

    ll ans=0;

    while(m--){

        a=gi(),b=gi(),c=gi(),f=gi();

        link(S,b,f,-100000000),link(a,T,f,-100000000);

        ans+=f*200000000ll;

        if(f<=c)link(a,b,c-f,1),link(a,b,1e9,2),link(b,a,f,1);

        else ans+=f-c,link(a,b,1e9,2),link(b,a,f-c,0),link(b,a,c,1);

    }

    link(n,1,1e9,0);

    while(Mincost(ans));printf("%lld\n",ans);

    return 0;

}

巴特西

CF708D Incorrect Flow

CF708D Incorrect Flow

最新文章

热门文章