题面

传送门

思路

第一问：无脑网络流跑一波

第二问：

先考虑一个贪心的结论：扩容出来的扩容流量一定要跑满

证明显然

因此我们可以把扩容费用可以换个角度思考，变成增加一点流量，花费W的费用

这样，我们就得到了一个最小费用流的模型

只要在原图基础上，对于每个原图边，加一条费用为W，无限容量的边，而原图中的所有边费用为0，就可以模拟原题需要的情况了

最后一个问题：流量增加限制K怎么处理？

我们虽然可以用spfa的费用流，一次一次增加，直到K，但是这样也太慢chou了吧？

不怕，我们加一个n+1号点，作为第二问的费用流汇点，在n到n+1之间连一条边，费用为0，流量为第一问的最大流流量加上K

注意：上述算法是对于第二问建一个新图来跑的，对于在残量网络上瞎搞的方法，由于本人水平有限，并无法很好地证明正确性

我的算法，时间复杂度大概会多一个$O\left(m\right)$，再加上一点常数

同时因为我是zkw费用流实现的最大流，所以大概稍慢....?

其实应该是一样的吧！

Code：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define inf 1e9

using namespace std;

inline int read(){

    int re=0,flag=1;char ch=getchar();

    while(ch>'9'||ch<'0'){

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

        ch=getchar();

    }

    while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();

    return re*flag;

}

int n,m,cnt=-1,ans,K,first[1010],dis[1010],vis[1010];

struct edge{

    int to,next,w,cap;

}a[25010];

inline void add(int u,int v,int w,int cap){

    a[++cnt]=(edge){v,first[u],w,cap};first[u]=cnt;

    a[++cnt]=(edge){u,first[v],-w,0};first[v]=cnt;

}

bool spfa(int s,int t){

    int q[5010],head=0,tail=1,u,v,w,i;

    memset(dis,-1,sizeof(dis));memset(vis,0,sizeof(vis));

    q[0]=t;dis[t]=0;vis[t]=1;

    while(head<tail){

        u=q[head++];vis[u]=0;

        for(i=first[u];~i;i=a[i].next){

            v=a[i].to;w=a[i].w;

            if(a[i^1].cap&&((dis[v]==-1)||(dis[v]>dis[u]-w))){

                dis[v]=dis[u]-w;

                if(!vis[v]) q[tail++]=v,vis[v]=1;

            }

        }

    }

    return ~dis[s];

}

int dfs(int u,int t,int limit){

    if(u==t){vis[t]=1;return limit;}

    if(!limit){vis[u]=1;return 0;}

    int i,v,f,flow=0,w;vis[u]=1;

    for(i=first[u];~i;i=a[i].next){

        v=a[i].to;w=a[i].w;

        if((dis[v]==dis[u]-w)&&(!vis[v])&&a[i].cap){

            f=dfs(v,t,min(limit,a[i].cap));if(!f) continue;

            a[i].cap-=f;a[i^1].cap+=f;

            flow+=f;limit-=f;ans+=a[i].w*f;

            if(!limit) return flow;

        }

    }

    return flow;

}

int zkw(int s,int t){//zkw费用流

    int re=0;

    while(spfa(s,t)){

        vis[t]=1;

        while(vis[t]){

            memset(vis,0,sizeof(vis));

            re+=dfs(s,t,inf);

            //cout<<"cur re="<<re<<"\n";

        }

    }

    return re;

}

int cost[5010],u[5010],v[5010],cap[5010];

int main(){

    memset(first,-1,sizeof(first));

    int i,maxflow;

    n=read();m=read();K=read();

    for(i=1;i<=m;i++){

        u[i]=read();v[i]=read();cap[i]=read();cost[i]=read();

        add(u[i],v[i],0,cap[i]);

    }

    printf("%d ",maxflow=zkw(1,n));//maxflow要记录下来，后面有用

    memset(first,-1,sizeof(first));memset(a,0,sizeof(a));cnt=-1;//清理原图，重新建图

    for(i=1;i<=m;i++){

        add(u[i],v[i],0,cap[i]);

        add(u[i],v[i],cost[i],inf);

    }

    add(n,n+1,0,maxflow+K);

    zkw(1,n+1);

    printf("%d",ans);

}

巴特西

[ZJOI2010][bzoj1834] 网络扩容 [费用流]

题面

思路

最新文章

热门文章