学习最小费用最大流前,需要学习最大流算法。在最大流算法中,没有考虑边的费用问题。在MinCostMaxFlow中,引入了费用的概念:cij表示边(i,j)单位流量的费用。在满足流量=v(f)的同时,并且要求费用最少。
最小费用最大流的迭代算法:
1.求出从s到t的最小费用通路(spfa)和通路的最大流量f。
2.让通路上的边(i,j)流量减去f;添加反向边(j,i),容量为f,费用为-cost(i,j)。
3.重复1,2,直到从s到t的流量=v(f)或者再也找不到从s到t的最小费用道路为止。
最小费用最大流算法还可以解决二分图最优匹配。
最小费用最大流模板:
const int size = 1102;
const int INF = 0x7fffffff;
struct Edge
{
int to;
int vol;
int cost;
int next;
}e[size*40];
int index[size];
int edgeNum;
int pre[size], pos[size];
int dis[size], que[size*10];
bool vis[size];
void insert(int from, int to, int vol, int cost)
{
e[edgeNum].to = to;
e[edgeNum].vol = vol;
e[edgeNum].cost = cost;
e[edgeNum].next = index[from];
index[from] = edgeNum++;
e[edgeNum].to = from;
e[edgeNum].vol = 0;
e[edgeNum].cost = -cost;
e[edgeNum].next = index[to];
index[to] = edgeNum++;
}
bool spfa(int s, int t)
{
int i;
memset(pre, -1, sizeof(pre));
memset(vis, 0, sizeof(vis));
int head, tail; head = tail = 0;
for(i = 0; i < size; i++)
dis[i] = INF;
que[tail++] = s;
pre[s] = s;
dis[s] = 0;
vis[s] = 1;
while(head != tail)
{
int now = que[head++];
vis[now] = 0;
for(i = index[now]; i != -1; i = e[i].next)
{
int adj = e[i].to;
if(e[i].vol > 0 && dis[now] + e[i].cost < dis[adj])
{
dis[adj] = dis[now] + e[i].cost;
pre[adj] = now;
pos[adj] = i;
if(!vis[adj])
{
vis[adj] = 1;
que[tail++] = adj;
}
}
}
}
return pre[t] != -1;
}
int MinCostFlow(int s, int t, int flow)
{
int i;
int cost = 0;
flow = 0;
while(spfa(s, t))
{
int f = INF;
for(i = t; i != s; i = pre[i])
if (e[pos[i]].vol < f) f = e[pos[i]].vol;
flow += f; cost += dis[t] * f;
for(i = t; i != s; i = pre[i])
{
e[pos[i]].vol -= f;
e[pos[i] ^ 1].vol += f;
}
}
return cost; // flow是最大流值
}
参见poj2516 2195 2135。
分享到:
相关推荐
网络流讲解之三——最大费用和最大流问题 希望对你的理解有所帮助
最大流问题:特殊的线性规划问题;是计算机科学和运筹学的研究内容;最大流实际上是在有容量限制的网络中求一个可行流,使其流量达到最大
网络流的经典例题,NOI大牛,ACM——专用
很开阔视野和思路的科普书籍:时间之箭——揭开时间最大奥秘之科学旅程
一种新型径向基函数神经网络学习算法 ———递归正交最小二乘法(ROLS)
网络信息安全——论文网络信息安全——论文网络信息安全——论文网络信息安全——论文网络信息安全——论文网络信息安全——论文
LVQ神经网络的预测——人脸朝向识别
一种新型的网络分布式计算——云计算一种新型的网络分布式计算——云计算
流病——简答.doc
算法(c++)——最小重量机器设计问题
基于改进粒子群算法的网络计划工期——费用优化.pdf
网络运维笔记——T221.pdf网络运维笔记——T221.pdf网络运维笔记——T221.pdf网络运维笔记——T221.pdf网络运维笔记——T221.pdf网络运维笔记——T221.pdf网络运维笔记——T221.pdf网络运维笔记——T221.pdf网络运维...
最大公约数、最小公倍数 * 最大公约数(a,b) * 12的因数:1、2、3、4、6、12 * 18的因数:1、2、3、6、9、18 * 12和18的最大公约数——6 * 最小公倍数[a,b] * A=2*3*7 * B=2*5*7 * AB的最小公倍数——2*3*5*7...
计算机网络课程设计——小型网络设计计算机网络课程设计——小型网络设计
五年级数学教案——最小公倍数练习八(二).doc
Linux安全操作系统构建方法与技术(第四讲)——最小特权管理.pdf
案例22 LVQ神经网络的预测——人脸朝向识别
MGUR在GRU的基础上进一步简化,只用一个门限控制前序信息的流动,其结构更简单,效果也不错。
网络程序设计——ASP(第3版)题解,绝对有用!!!!