模板——最小费用最大流

淡淡的烟草味﹌ 2021-11-01 13:24 363阅读 0赞

传送门：[QAQQAQ][]

因为要在最大流的情况下，保证最小费用，所以我们在增广时就用SPFA跑一个最短路进行增广，虽然这个路径可能不在最大流中，但残量网络可以保证我们这个“可以反悔的贪心”不会出错~

具体写法：SPFA+EK

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    #define mk make_pair
    using namespace std;
    typedef pair<int,int> pii;
    const int inf=(int)2e9; 
    const int N=1020*50;
    
    int n,m,s,t;
    int first[N*2],nxt[N*4],point[N*4],cost[N*4],flow[N*4],e=0;
    void add(int x,int y,int z,int c)
    {
        nxt[e]=first[x];
        first[x]=e;
        point[e]=y;
        cost[e]=c;
        flow[e]=z; e++;
    }
    void add_edge(int x,int y,int z,int c)
    {
        add(x,y,z,c);
        add(y,x,0,-c); 
    }
    
    int dis[N],inq[N],pre_point[N],f[N],pre_edge[N];
    void init_SPFA()
    {
        for(int i=1;i<=n;i++) dis[i]=inf,f[i]=inf;
        for(int i=1;i<=n;i++) inq[i]=0;
        memset(pre_point,-1,sizeof(pre_point));
        memset(pre_edge,-1,sizeof(pre_edge));
    }
    
    queue<int> q;
    bool SPFA()
    {
        init_SPFA();
        q.push(s); inq[s]=1; dis[s]=0;
        while(!q.empty())
        {
            int now=q.front(); q.pop();
            inq[now]=0;
            for(int i=first[now];i!=-1;i=nxt[i])
            {
                int pos=point[i];
                if(flow[i]==0) continue;
                if(dis[pos]>dis[now]+cost[i])
                {
                    dis[pos]=dis[now]+cost[i];
                    pre_point[pos]=now;
                    pre_edge[pos]=i;
                    f[pos]=min(flow[i],f[now]);
                    if(!inq[pos])
                    {
                        inq[pos]=1;
                        q.push(pos);
                    }
                }
            }
        }
        return pre_point[t]!=-1;
    }
    
    pii solve()
    {
        int max_flow=0,min_cost=0;
        int tot=0;
        while(SPFA())
        {
            min_cost+=dis[t]*f[t];
            max_flow+=f[t];
            int now=t;
            while(now!=s)
            {
                int E=pre_edge[now];
                flow[E]-=f[t];
                flow[E^1]+=f[t];
                now=pre_point[now];
            }
        }
        return mk(max_flow,min_cost);
    }
    
    void init()
    {
        memset(first,-1,sizeof(first));
        memset(nxt,-1,sizeof(nxt));
        scanf("%d%d%d%d",&n,&m,&s,&t);
        for(int i=1;i<=m;i++)//之前写成n了啊啊啊 
        {
            int x,y,z,c;
            scanf("%d%d%d%d",&x,&y,&z,&c);
            add_edge(x,y,z,c);
        }
    }
    
    int main()
    {
        init();
        pii ans=solve();
        cout<<ans.first<<" "<<ans.second<<endl;
    }

再来一道题：

传送门：[QAQQAQ][QAQQAQ 1]

题意：有$n$个盒子(1<=$n$<=1000)围成一个圈,每个盒子有$a\_\{i\}$个球,所有盒子的球的总数小于等于$n$.每一次移动,可以把一个球移动到它的一个相邻的盒子内.  
现在要使得每个盒子的球数$<=1$,求最少的移动次数

思路：直接说建图吧（网络流主要就是难在建图）

我们造一个源点，一个汇点，源点和每一个点连一条容量为$a\_\{i\}$，费用为$0$的边，汇点和每一个点连一条容量为$1$，费用为$0$的边，对于中间的点，我们对于它和它左右两点各连一条容量为$inf$，费用为$1$的边。

这样我们跑一遍最小费用最大流即可（即在总流量为$sumball$的情况下，费用最小）

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    #define mk make_pair
    using namespace std;
    typedef pair<int,int> pii;
    const int inf=(int)2e9;
    const int N=100020;
     
    int n,m,s,t;
    int first[N*2],nxt[N*4],point[N*4],cost[N*4],flow[N*4],e=0;
    void add(int x,int y,int z,int c)
    {
        nxt[e]=first[x];
        first[x]=e;
        point[e]=y;
        cost[e]=c;
        flow[e]=z; e++;
    }
    void add_edge(int x,int y,int z,int c)
    {
        add(x,y,z,c);
        add(y,x,0,-c);
    }
     
    int dis[N],inq[N],pre_point[N],f[N],pre_edge[N];
    void init_SPFA()
    {
        for(int i=0;i<=n+1;i++) dis[i]=inf,f[i]=inf;
        for(int i=0;i<=n+1;i++) inq[i]=0;
        memset(pre_point,-1,sizeof(pre_point));
        memset(pre_edge,-1,sizeof(pre_edge));
    }
     
    queue<int> q;
    bool SPFA()
    {
        init_SPFA();
        q.push(s); inq[s]=1; dis[s]=0;
        while(!q.empty())
        {
            int now=q.front(); q.pop();
            inq[now]=0;
            for(int i=first[now];i!=-1;i=nxt[i])
            {
                int pos=point[i];
                if(flow[i]==0) continue;
                if(dis[pos]>dis[now]+cost[i])
                {
                    dis[pos]=dis[now]+cost[i];
                    pre_point[pos]=now;
                    pre_edge[pos]=i;
                    f[pos]=min(flow[i],f[now]);
                    if(!inq[pos])
                    {
                        inq[pos]=1;
                        q.push(pos);
                    }
                }
            }
        }
        return pre_point[t]!=-1;
    }
     
    int solve()
    {
        int max_flow=0,min_cost=0;
        int tot=0;
        while(SPFA())
        {
            min_cost+=dis[t]*f[t];//是单位费用，所以要乘
            max_flow+=f[t];
            int now=t;
            while(now!=s)
            {
                int E=pre_edge[now];
                flow[E]-=f[t];
                flow[E^1]+=f[t];
                now=pre_point[now];
            }
        }
        return min_cost;
    }
     
    int a[N];
    void init()
    {
        memset(first,-1,sizeof(first));
        memset(nxt,-1,sizeof(nxt));
        scanf("%d",&n);
        s=0,t=n+1;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
        {
            add_edge(s,i,a[i],0);
            add_edge(i,t,1,0);
            int l=i-1,r=i+1;
            if(i==1) l=n; if(i==n) r=1;
            add_edge(i,l,inf,1);
            add_edge(i,r,inf,1);
        }
    }
     
    int main()
    {
        init();
        int ans=solve();
        cout<<ans<<endl;
    }

转载于:https://www.cnblogs.com/Forever-666/p/11279706.html

[QAQQAQ]: https://www.luogu.org/problem/P3381
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/3c161fffab3c4ed99265964e37e38285.png
[QAQQAQ 1]: https://dev.xjoi.net/contest/1205/problem/2