技术标签： # ACM-图论 算法 费用流 网络流 SPFA
所谓最小费用最大流，其实就是在最大流问题的基础上，再给边加上一个属性：单位流量的费用。边的容量为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;
#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;
}
题意就是n个房子，有n个人，使每个人都进入一个房子内，一个房子只能进一个人，求所有人走完的最少步数(最小花费)。
怎么建图呢？
建成了一张普通的图，然后跑一遍 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;
}
题意：
给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(V2*E)，25003 数据量，肯定超时了）
简化一下：输出-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
文章浏览阅读1k次。通过使用ajax方法跨域请求是浏览器所不允许的，浏览器出于安全考虑是禁止的。警告信息如下：不过jQuery对跨域问题也有解决方案，使用jsonp的方式解决，方法如下：$.ajax({ async:false, url: 'http://www.mysite.com/demo.do', // 跨域URL ty..._nginx不停的xhr
文章浏览阅读2k次。关于在 Oracle 中配置 extproc 以访问 ST_Geometry，也就是我们所说的 使用空间SQL 的方法，官方文档链接如下。http://desktop.arcgis.com/zh-cn/arcmap/latest/manage-data/gdbs-in-oracle/configure-oracle-extproc.htm其实简单总结一下，主要就分为以下几个步骤。..._extproc
文章浏览阅读1.5w次。linux下没有上面的两个函数，需要使用函数 mbstowcs和wcstombsmbstowcs将多字节编码转换为宽字节编码wcstombs将宽字节编码转换为多字节编码这两个函数，转换过程中受到系统编码类型的影响，需要通过设置来设定转换前和转换后的编码类型。通过函数setlocale进行系统编码的设置。linux下输入命名locale -a查看系统支持的编码_linux c++ gbk->utf8
文章浏览阅读750次。今天准备从生产库向测试库进行数据导入，结果在imp导入的时候遇到“ IMP-00009:导出文件异常结束” 错误，google一下，发现可能有如下原因导致imp的数据太大，没有写buffer和commit两个数据库字符集不同从低版本exp的dmp文件，向高版本imp导出的dmp文件出错传输dmp文件时，文件损坏解决办法：imp时指定..._imp-00009导出文件异常结束
文章浏览阅读143次。当下是一个大数据的时代，各个行业都离不开数据的支持。因此，网络爬虫就应运而生。网络爬虫当下最为火热的是Python，Python开发爬虫相对简单，而且功能库相当完善，力压众多开发语言。本次教程我们爬取前程无忧的招聘信息来分析Python程序员需要掌握那些编程技术。首先在谷歌浏览器打开前程无忧的首页，按F12打开浏览器的开发者工具。浏览器开发者工具是用于捕捉网站的请求信息，通过分析请求信息可以了解请..._初级python程序员能力要求
文章浏览阅读7.6k次，点赞2次，收藏6次。@Service标注的bean，类名：ABDemoService查看源码后发现，原来是经过一个特殊处理：当类的名字是以两个或以上的大写字母开头的话，bean的名字会与类名保持一致public class AnnotationBeanNameGenerator implements BeanNameGenerator { private static final String C..._@service beanname
文章浏览阅读6.9w次，点赞73次，收藏463次。1.前序创建#include<stdio.h>#include<string.h>#include<stdlib.h>#include<malloc.h>#include<iostream>#include<stack>#include<queue>using namespace std;typed_二叉树的建立
文章浏览阅读7.1k次。在Asp.net上使用Excel导出功能，如果文件名出现中文，便会以乱码视之。 解决方法： fileName = HttpUtility.UrlEncode(fileName, System.Text.Encoding.UTF8);_asp.net utf8 导出中文字符乱码
文章浏览阅读2.1k次，点赞4次，收藏23次。第一次实验 词法分析实验报告设计思想词法分析的主要任务是根据文法的词汇表以及对应约定的编码进行一定的识别，找出文件中所有的合法的单词，并给出一定的信息作为最后的结果，用于后续语法分析程序的使用；本实验针对 PL/0 语言 的文法、词汇表编写一个词法分析程序，对于每个单词根据词汇表输出： (单词种类, 单词的值) 二元对。词汇表：种别编码单词符号助记符0beginb..._对pl/0作以下修改扩充。增加单词
文章浏览阅读773次。我在使用adb.exe时遇到了麻烦.我想使用与bash相同的adb.exe shell提示符,所以我决定更改默认的bash二进制文件(当然二进制文件是交叉编译的,一切都很完美)更改bash二进制文件遵循以下顺序> adb remount> adb push bash / system / bin /> adb shell> cd / system / bin> chm..._adb shell mv 权限
文章浏览阅读6.8k次，点赞12次，收藏125次。1. 单目相机标定引言相机标定已经研究多年，标定的算法可以分为基于摄影测量的标定和自标定。其中，应用最为广泛的还是张正友标定法。这是一种简单灵活、高鲁棒性、低成本的相机标定算法。仅需要一台相机和一块平面标定板构建相机标定系统，在标定过程中，相机拍摄多个角度下（至少两个角度，推荐10~20个角度）的标定板图像（相机和标定板都可以移动），即可对相机的内外参数进行标定。下面介绍张氏标定法（以下也这么称呼）的原理。原理相机模型和单应矩阵相机标定，就是对相机的内外参数进行计算的过程，从而得到物体到图像的投影_相机-投影仪标定
文章浏览阅读2.2k次。文章目录Wayland 架构Wayland 渲染Wayland的 硬件支持简 述： 翻译一篇关于和 wayland 有关的技术文章, 其英文标题为Wayland Architecture .Wayland 架构若是想要更好的理解 Wayland 架构及其与 X (X11 or X Window System) 结构；一种很好的方法是将事件从输入设备就开始跟踪, 查看期间所有的屏幕上出现的变化。这就是我们现在对 X 的理解。 内核是从一个输入设备中获取一个事件，并通过 evdev 输入_wayland