本文 前置基础:最大流问题(Dinic算法) && 单源最短路径(SPFA算法)


洛谷 P3381 【模板】最小费用最大流

所谓最小费用最大流,其实就是在最大流问题的基础上,再给边加上一个属性:单位流量的费用。边的容量为cap,单位流量的费用为cost,需要求出在最大流的前提下,最小的总费用。(总流量最大并且总费用最小)

每条增广路上的费用 = 这条路上的最小流量 * 所有边的单位流量费用之和。

从原先Dinic算法的模板来看(最大流Dinic模板),有BFS来求分层图,并DFS进行增广。
现在我们需要保证“最小花费”,并且DFS搜索出“最大流量”,这样就是完成了任务。而要求最小花费,显然可以跑最短路,将原先的 普通BFS 升级改造成 SPFA算法 来解决这一问题。SPFA还是和之前BFS一样,充当“探路”和“分层”的工作,与之前不同的是,现在还能保证求出单位流量费用的最短路。

原来的BFS是用dep数组进行分层,在DFS中有 dep[v]==dep[u]+1 这一条件来进行约束求增广路,
现在定义一个dis数组表示到某个点的最小的单位流量费用之和,那么DFS中分层约束条件改成 dis[v]==dis[u]+e[i].cap;

在加反向边的过程中,反向边容量还是0,但是引入了费用,费用必须是正向边的相反数(负数)才能保证能“反悔”找到最大流,所以显然这是一个含有负权边的图,而Dijkstra是不能跑负权边的(经过一些处理变为正权边也行,但是在此只提供SPFA写法)。

至于求最小花费,就是在DFS回溯过程中进行累加即可:mincost+=di*e[i].cost;

AC代码(Dinic思路 + SPFA)

#include <bits/stdc++.h>
using namespace std;
const int N=5e3+10,M=5e4+10,inf=0x7f7f7f7f;
//(1<<31)-1  2147483647
//0x7f7f7f7f 2139062143
//0x3f3f3f3f 1061109567
int n,m,s,t,cnt,mincost,head[N],dis[N],vis[N],cur[N];
struct edge
{
    int to,next,cap,cost;//cap是容量,cost是单位流量的花费
}e[M<<1];
void add(int x,int y,int z,int c)
{
    e[cnt].to=y;
    e[cnt].cap=z;
    e[cnt].cost=c;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
void add_edge(int x,int y,int z,int c)
{
    add(x,y,z,c);
    add(y,x,0,-c);//反向边容量为0,单位流量的花费为-c
}
bool spfa()
{
    queue<int>q;
    memset(dis,inf,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    vis[s]=1;//入队标记
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;//出队标记
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            int v=e[i].to;
            if(e[i].cap>0&&dis[u]+e[i].cost<dis[v])
            {
                dis[v]=dis[u]+e[i].cost;
                if(!vis[v])
                {
                    vis[v]=1;//入队标记
                    q.push(v);
                }
            }
        }
    }//队列为空时 vis也全部被置为0
    if(dis[t]!=inf)return 1;
    return 0;
}
int dfs(int u,int flow)
{
    vis[u]=1;//注意用vis标记走过的点,防止死循环
    if(u==t)return flow;//到达汇点,返回这条增广路上的最小流量
    for(int& i=cur[u];i!=-1;i=e[i].next)
    //当前弧优化,cur[u]表示u开始的边
    //每一次dfs增广时不从第一条边开始,而是用一个数组cur记录点u之前循环到了哪一条边
    //下次再遍历就不是从第一条边head[u]开始,而是从上次遍历到的最后一条边开始
    //&表示引用,即cur[u]的值会随i同时变化
    {
        int v=e[i].to;
        if(e[i].cap>0&&dis[v]==dis[u]+e[i].cost&&!vis[v])
        {
            int di=dfs(v,min(flow,e[i].cap));//min(flow,e[i].w)表示起点到v的最小流量
            if(di>0)//防止dfs结果return 0的情况,如果di=0会死循环
            {
                e[i].cap-=di;
                e[i^1].cap+=di;//反向边加上di
                mincost+=di*e[i].cost;
                return di;//di表示整条增广路上的最小流量,回溯的时候一直向上返回,返回的di是不变的
            }
        }
    }
    vis[u]=0;//还原标记的点
    return 0;//找不到增广路,到不了汇点
}
int dinic()
{
    int maxflow=0;
    while(spfa())//先spfa进行“探路”并分层,分层后进行多次dfs
    {
        memcpy(cur,head,sizeof(head));//cur初始化
        while(int d=dfs(s,inf))//while循环的意义:只要dfs不为0,就一直dfs,直到找不到增广路
            maxflow+=d;
    }
    return maxflow;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>s>>t;
    int x,y,z,c;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z>>c;
        add_edge(x,y,z,c);
    }
    int maxflow=dinic();
    printf("%d %d\n",maxflow,mincost);
    return 0;
}

POJ 2195 Going Home

题意就是n个房子,有n个人,使每个人都进入一个房子内,一个房子只能进一个人,求所有人走完的最少步数(最小花费)。

怎么建图呢?
1. 加个源点s,由源点出发连接所有人,容量1,费用0(这样就不用考虑多出来边的花费);
2. 加个汇点t,所有房子汇聚到t,容量1,费用0;
3. 人和房子连边,如果先不考虑最短距离,每个人实际上是有走n个房子的可能性,所以一个人就可以连n条边,n个人就可以连n*n条边,由此可见人与房子连边的可能性是多对多的关系。为了保证人和房子是一对一的关系,把容量定为1;而边的单位流量费用就是这两个点的曼哈顿距离,即两点间: |横坐标的差| + |纵坐标的差| 。

建成了一张普通的图,然后跑一遍 Dinic+SPFA 求出最大流中的最小费用即可。

这样就能保证在最后的残留网络中,每个人只能连一个房子,人和房子是唯一对应的,并且总花费最小。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N=210,M=1e5+10,inf=0x7f7f7f7f;//N记得开200,不是100
//(1<<31)-1  2147483647
//0x7f7f7f7f 2139062143
//0x3f3f3f3f 1061109567
int n,m,s,t,cnt,mincost,head[N],dis[N],vis[N],cur[N];
struct edge
{
    int to,next,cap,cost;
}e[M<<1];
struct node
{
    int x,y;
};
vector<node>man,home;
void add(int x,int y,int z,int c)
{
    e[cnt].to=y;
    e[cnt].cap=z;
    e[cnt].cost=c;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
void add_edge(int x,int y,int z,int c)
{
    add(x,y,z,c);
    add(y,x,0,-c);
}
bool spfa()
{
    queue<int>q;
    memset(dis,inf,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0;//s到自身最短路为0
    vis[s]=1;//入队标记
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;//出队标记
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            int v=e[i].to;
            if(e[i].cap>0&&dis[u]+e[i].cost<dis[v])
            {
                dis[v]=dis[u]+e[i].cost;
                if(!vis[v])
                {
                    vis[v]=1;//入队标记
                    q.push(v);
                }
            }
        }
    }//队列为空时 vis也全部被置为0
    if(dis[t]!=inf)return 1;
    return 0;
}
int dfs(int u,int flow)
{
    vis[u]=1;
    if(u==t)return flow;//到达汇点,返回这条增广路上的最小流量
    for(int& i=cur[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        if(e[i].cap>0&&dis[v]==dis[u]+e[i].cost&&!vis[v])
        {
            int di=dfs(v,min(flow,e[i].cap));//min(flow,e[i].w)表示起点到v的最小流量
            if(di>0)//防止dfs结果return 0的情况,如果di=0会死循环
            {
                e[i].cap-=di;
                e[i^1].cap+=di;//反向边加上di
                mincost+=di*e[i].cost;
                return di;//di表示整条增广路上的最小流量,回溯的时候一直向上返回,返回的di是不变的
            }
        }
    }
    vis[u]=0;
    return 0;//找不到增广路,到不了汇点
}
int dinic()
{
    int maxflow=0;
    while(spfa())//先spfa进行“探路”并分层,分层后进行多次dfs
    {
        memcpy(cur,head,sizeof(head));
        while(int d=dfs(s,inf))//while循环的意义:只要dfs不为0,就一直dfs,直到找不到增广路
            maxflow+=d;
    }
    return maxflow;
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>m&&(n||m))
    {
        cnt=0;
        memset(head,-1,sizeof(head));
        man.clear();
        home.clear();
        char c;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                cin>>c;//不用开数组存矩阵
                if(c=='m')man.push_back({i,j});
                if(c=='H')home.push_back({i,j});
            }
        int numm=man.size();
        int numh=home.size();
        s=0,t=numh+numm+1;
        for(int i=0;i<numm;i++)
        {
            int manid=i+1;
            add_edge(s,manid,1,0);//源点与人连边,容量是1,花费是0
            for(int j=0;j<numh;j++)
            {
                int mx=man[i].x;
                int my=man[i].y;
                int hx=home[j].x;
                int hy=home[j].y;
                int cost=abs(mx-hx)+abs(my-hy);
                int homeid=j+1+numm;
                add_edge(manid,homeid,1,cost);
                //人与房子连边,容量是1,花费是两点间曼哈顿距离
            }
        }
        for(int i=0;i<numh;i++)
        {
            int homeid=i+1+numm;
            add_edge(homeid,t,1,0);//房子与汇点连边,容量是1,花费是0
        }
        mincost=0;
        dinic();//函数返回maxflow,但是这题并不要求maxflow,只要求mincost
        printf("%d\n",mincost);
    }
    return 0;
}

POJ 2516 Minimum Cost

题意:

给n,m,k表示商店数,储存店数,种类数

然后给n*k表示每个商店需求每种种类的数量: 表示为a[i][j]

再给m*k表示每个储存店每种种类数量: 表示为b[i][j]

再给k个n*m的矩阵,第 p 种商店从 j 储物店运送到 i 商店的单位价格:表示为cost[p][i][j]

思路:
一下把图建完会TLE,因为点和边太多了(虽然数据看起来好像只有50,平方就是2500,实际上点V和边E都近似有2500,时间复杂度O(V^2^*E),2500^3^ 数据量,肯定超时了)
简化一下:输出-1的情况是供给小于需求,其他情况就是跑k次费用流,分别以每一种物品独立的跑。因为物品之间是相互独立的,所以可以独立的跑。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N=52,V=2*N,M=1e4+10,inf=0x7f7f7f7f;
int n,m,k,s,t,cnt,mincost,head[V+10],dis[V+10],vis[V+10],cur[V+10];
int a[N][N],b[N][N],cost[N][N][N];
int sum1[N],sum2[N];
struct edge
{
    int to,next,cap,cost;//cap是容量,cost是单位流量的花费
}e[M<<1];
void add(int x,int y,int z,int c)
{
    e[cnt].to=y;
    e[cnt].cap=z;
    e[cnt].cost=c;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
void add_edge(int x,int y,int z,int c)
{
    add(x,y,z,c);
    add(y,x,0,-c);
}
bool spfa()
{
    queue<int>q;
    memset(dis,inf,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    vis[s]=1;//入队标记
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;//出队标记
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            int v=e[i].to;
            if(e[i].cap>0&&dis[u]+e[i].cost<dis[v])
            {
                dis[v]=dis[u]+e[i].cost;
                if(!vis[v])
                {
                    vis[v]=1;//入队标记
                    q.push(v);
                }
            }
        }
    }//队列为空时 vis也全部被置为0
    if(dis[t]!=inf)return 1;
    return 0;
}
int dfs(int u,int flow)
{
    vis[u]=1;//注意用vis标记走过的点,防止死循环
    if(u==t)return flow;//到达汇点,返回这条增广路上的最小流量
    for(int& i=cur[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        if(e[i].cap>0&&dis[v]==dis[u]+e[i].cost&&!vis[v])
        {
            int di=dfs(v,min(flow,e[i].cap));//min(flow,e[i].w)表示起点到v的最小流量
            if(di>0)//防止dfs结果return 0的情况,如果di=0会死循环
            {
                e[i].cap-=di;
                e[i^1].cap+=di;//反向边加上di
                mincost+=di*e[i].cost;
                return di;//di表示整条增广路上的最小流量,回溯的时候一直向上返回,返回的di是不变的
            }
        }
    }
    vis[u]=0;//还原标记的点
    return 0;//找不到增广路,到不了汇点
}
int dinic()
{
    int maxflow=0;
    while(spfa())//先spfa进行“探路”并分层,分层后进行多次dfs
    {
        memcpy(cur,head,sizeof(head));
        while(int d=dfs(s,inf))//while循环的意义:只要dfs不为0,就一直dfs,直到找不到增广路
            maxflow+=d;
    }
    return maxflow;
}
int cal(int p)//第p个物品相应连边后跑费用流
{
    if(sum1[p]>sum2[p])return -1;//sum1需求 sum2供给
    //只要供给大于等于需求,这个物品的条件就可以被满足
    memset(head,-1,sizeof(head));
    cnt=0;
    s=0,t=V;
    for(int i=1;i<=n;i++)
        add_edge(i+m,t,a[i][p],0);//收货点与汇点相连
    for(int i=1;i<=m;i++)
        add_edge(s,i,b[i][p],0);//源点与供货点相连
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            add_edge(j,i+m,inf,cost[p][i][j]);//供货点与收货点连边,流量为inf
    dinic();
    return mincost;
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>m>>k&&(n||m||k))
    {
        memset(sum1,0,sizeof(sum1));
        memset(sum2,0,sizeof(sum2));
        for(int i=1;i<=n;i++)//需求
            for(int j=1;j<=k;j++)
                cin>>a[i][j],sum1[j]+=a[i][j];
        for(int i=1;i<=m;i++)//供给
            for(int j=1;j<=k;j++)
                cin>>b[i][j],sum2[j]+=b[i][j];
        for(int p=1;p<=k;p++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                    cin>>cost[p][i][j];//第p个矩阵,表示j->i运送第p个物品的费用
        mincost=0;//跑费用流之前,记得先把mincost初始化为0
        int ans;
        for(int i=1;i<=k;i++)//跑k个物品的费用流
        {
            ans=cal(i);
            if(ans==-1)break;
        }
        printf("%d\n",ans);
    }
    return 0;
}

测试数据:

2 4 3
0 2 3
2 3 4
1 0 2
1 0 3
0 2 4
2 3 0
2 3 1 2
1 2 3 1
1 1 2 3
2 1 3 1
2 2 3 1
2 3 4 1
0 0 0
ans:27

2 4 5
2 1 2 2 2
1 1 1 2 1
2 2 2 2 2
2 1 2 1 1
2 2 2 2 1
1 2 2 2 1
1 1 6 7
5 5 2 9
4 6 6 9
9 1 9 1
7 4 1 7
4 4 7 3
5 4 7 7
9 1 3 8
8 8 2 7
1 4 7 1
0 0 0
ans:38