http://www.artofproblemsolving.com/blog/54262
这个是原作者的博文地址
这是今天刚学的,不过理解上还是很浅薄。最近发现算法不能融会贯通还是因为自己太死板了。
奉上一个基础版本的模板, POJ 2195 的代码。
本模板是不能直接用于任何有负权的图,更不能用于有负圈的情况
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 222
#define MAXM 55555
#define INF 1000000007
using namespace std;
struct EDGE
{
int cost, cap, v;
int next, re;
}edge[MAXM];
int head[MAXN], e;
int vis[MAXN];
int ans, cost, src, des, n;
void init()
{
memset(head, -1, sizeof(head));
e = 0;
ans = cost = 0;
}
void add(int u, int v, int cap, int cost)
{
edge[e].v = v;
edge[e].cap = cap;
edge[e].cost = cost;
edge[e].re = e + 1;
edge[e].next = head[u];
head[u] = e++;
edge[e].v = u;
edge[e].cap = 0;
edge[e].cost = -cost;
edge[e].re = e - 1;
edge[e].next = head[v];
head[v] = e++;
}
int aug(int u, int f)
{
if(u == des)
{
ans += cost * f;
return f;
}
vis[u] = 1;
int tmp = f;
for(int i = head[u]; i != -1; i = edge[i].next)
if(edge[i].cap && !edge[i].cost && !vis[edge[i].v])
{
int delta = aug(edge[i].v, tmp < edge[i].cap ? tmp : edge[i].cap);
edge[i].cap -= delta;
edge[edge[i].re].cap += delta;
tmp -= delta;
if(!tmp) return f;
}
return f - tmp;
}
bool modlabel()
{
int delta = INF;
for(int u = 1; u <= n; u++)
if(vis[u])
for(int i = head[u]; i != -1; i = edge[i].next)
if(edge[i].cap && !vis[edge[i].v] && edge[i].cost < delta) delta = edge[i].cost;
if(delta == INF) return false;
for(int u = 1; u <= n; u++)
if(vis[u])
for(int i = head[u]; i != -1; i = edge[i].next)
edge[i].cost -= delta, edge[edge[i].re].cost += delta;
cost += delta;
return true;
}
void costflow()
{
do
{
do
{
memset(vis, 0, sizeof(vis));
}while(aug(src, INF));
}while(modlabel());
}
int nt, m;
struct point
{
int x, y;
}p[MAXN], h[MAXN];
int d[MAXN][MAXN];
char s[MAXN][MAXN];
int main()
{
while(scanf("%d%d", &m, &nt) != EOF)
{
if(m == 0 && nt == 0) break;
for(int i = 0; i < m; i++)
scanf("%s", s[i]);
int hcnt = 0, pcnt = 0;
for(int i = 0; i < m; i++)
for(int j = 0; j < nt; j++)
{
if(s[i][j] == 'H')
{
hcnt++;
h[hcnt].x = i;
h[hcnt].y = j;
}
else if(s[i][j] == 'm')
{
pcnt++;
p[pcnt].x = i;
p[pcnt].y = j;
}
}
for(int i = 1; i <= pcnt; i++)
for(int j = 1; j <= hcnt; j++)
d[i][j] = abs(p[i].x - h[j].x) + abs(p[i].y - h[j].y);
init();
n = hcnt + pcnt + 2;
src = hcnt + pcnt + 1;
des = n;
for(int i = 1; i <= pcnt; i++)
for(int j = 1; j <= hcnt; j++)
add(i, j + pcnt, 1, d[i][j]);
for(int i = 1; i <= pcnt; i++)
add(src, i, 1, 0);
for(int i = 1; i <= hcnt; i++)
add(i + pcnt, des, 1, 0);
costflow();
printf("%d\n", ans);
}
return 0;
}
然后再来一个最基础的模板
这个模板呢,跟上一个一样的地方就是初始化,src代表起点,des是终点,n是顶点的个数
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 5555
#define MAXM 55555
#define INF 100000007
using namespace std;
struct EDGE
{
int v, cap, cost, next, re; // re记录逆边的下标。
} edge[MAXM];
int n, m, ans, flow, src, des;
int e, head[MAXN];
int que[MAXN], pre[MAXN], dis[MAXN];
bool vis[MAXN];
void init()
{
e = ans = flow = 0;
memset(head, -1, sizeof(head));
}
void add(int u, int v, int cap, int cost)
{
edge[e].v = v;
edge[e].cap = cap;
edge[e].cost = cost;
edge[e].next = head[u];
edge[e].re = e + 1;
head[u] = e++;
edge[e].v = u;
edge[e].cap = 0;
edge[e].cost = -cost;
edge[e].next = head[v];
edge[e].re = e - 1;
head[v] = e++;
}
bool spfa()
{
int i, h = 0, t = 1;
for(i = 0; i <= n; i ++)
{
dis[i] = INF;
vis[i] = false;
}
dis[src] = 0;
que[0] = src;
vis[src] = true;
while(t != h)
{
int u = que[h++];
h %= n;
vis[u] = false;
for(i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if(edge[i].cap && dis[v] > dis[u] + edge[i].cost)
{
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if(!vis[v])
{
vis[v] = true;
que[t++] = v;
t %= n;
}
}
}
}
if(dis[des] == INF) return false;
return true;
}
void end()
{
int u, p, mi = INF;
for(u = des; u != src; u = edge[edge[p].re].v)
{
p = pre[u];
mi = min(mi, edge[p].cap);
}
for(u = des; u != src; u = edge[edge[p].re].v)
{
p = pre[u];
edge[p].cap -= mi;
edge[edge[p].re].cap += mi;
ans += mi * edge[p].cost; // cost记录的为单位流量费用,必须得乘以流量。
}
flow += mi;
}
int nt, k;
void build()
{
init();
int w;
for(int i = 1; i <= nt; i++)
for(int j = 1; j <= nt; j++)
{
scanf("%d", &w);
int id = (i - 1) * nt + j;
add(id, id + nt * nt, 1, -w);
add(id, id + nt * nt, k, 0);
if(i < nt) add(id + nt * nt, id + nt, k, 0);
if(j < nt) add(id + nt * nt, id + 1, k, 0);
}
src = nt * nt * 2 + 1;
des = nt * nt * 2 + 2;
n = des;
add(src, 1, k, 0);
add(nt * nt * 2, des, k, 0);
}
void MCMF()
{
init();
build();
while(spfa()) end();
}
int main()
{
while(scanf("%d%d", &nt, &k) != EOF)
{
MCMF();
printf("%d\n", -ans);
}
return 0;
}
最后来一个使用 Small Label First 优化
的 SPFA 来维护 zkw 算法中的距离标号, 保留多路增广
这也是根据原作者的程序改的,这个貌似就可以用负的边权了
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <deque>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 555
#define MAXM 55555
#define INF 100000007
using namespace std;
struct EDGE
{
int cost, cap, v;
int next, re;
}edge[MAXM];
int head[MAXN], e;
int vis[MAXN], d[MAXN];
int ans, cost, src, des, n;
void init()
{
memset(head, -1, sizeof(head));
e = 0;
ans = cost = 0;
}
void add(int u, int v, int cap, int cost)
{
edge[e].v = v;
edge[e].cap = cap;
edge[e].cost = cost;
edge[e].re = e + 1;
edge[e].next = head[u];
head[u] = e++;
edge[e].v = u;
edge[e].cap = 0;
edge[e].cost = -cost;
edge[e].re = e - 1;
edge[e].next = head[v];
head[v] = e++;
}
int aug(int u, int f)
{
if(u == des)
{
ans += cost * f;
return f;
}
vis[u] = 1;
int tmp = f;
for(int i = head[u]; i != -1; i = edge[i].next)
if(edge[i].cap && !edge[i].cost && !vis[edge[i].v])
{
int delta = aug(edge[i].v, tmp < edge[i].cap ? tmp : edge[i].cap);
edge[i].cap -= delta;
edge[edge[i].re].cap += delta;
tmp -= delta;
if(!tmp) return f;
}
return f - tmp;
}
bool modlabel()
{
for(int i = 0; i <= n; i++) d[i] = INF;
d[des] = 0;
deque<int>Q;
Q.push_back(des);
while(!Q.empty())
{
int u = Q.front(), tmp;
Q.pop_front();
for(int i = head[u]; i != -1; i = edge[i].next)
if(edge[edge[i].re].cap && (tmp = d[u] - edge[i].cost) < d[edge[i].v])
(d[edge[i].v] = tmp) <= d[Q.empty() ? src : Q.front()] ? Q.push_front(edge[i].v) : Q.push_back(edge[i].v);
}
for(int u = 1; u <= n; u++)
for(int i = head[u]; i != -1; i = edge[i].next)
edge[i].cost += d[edge[i].v] - d[u];
cost += d[src];
return d[src] < INF;
}
void costflow()
{
while(modlabel())
{
do
{
memset(vis, 0, sizeof(vis));
}while(aug(src, INF));
}
}
int nt, m;
struct point
{
int x, y;
}p[MAXN], h[MAXN];
int dis[MAXN][MAXN];
char s[MAXN][MAXN];
int main()
{
while(scanf("%d%d", &m, &nt) != EOF)
{
if(m == 0 && nt == 0) break;
for(int i = 0; i < m; i++)
scanf("%s", s[i]);
int hcnt = 0, pcnt = 0;
for(int i = 0; i < m; i++)
for(int j = 0; j < nt; j++)
{
if(s[i][j] == 'H')
{
hcnt++;
h[hcnt].x = i;
h[hcnt].y = j;
}
else if(s[i][j] == 'm')
{
pcnt++;
p[pcnt].x = i;
p[pcnt].y = j;
}
}
for(int i = 1; i <= pcnt; i++)
for(int j = 1; j <= hcnt; j++)
dis[i][j] = abs(p[i].x - h[j].x) + abs(p[i].y - h[j].y);
init();
n = hcnt + pcnt + 2;
src = hcnt + pcnt + 1;
des = n;
for(int i = 1; i <= pcnt; i++)
for(int j = 1; j <= hcnt; j++)
add(i, j + pcnt, 1, dis[i][j]);
for(int i = 1; i <= pcnt; i++)
add(src, i, 1, 0);
for(int i = 1; i <= hcnt; i++)
add(i + pcnt, des, 1, 0);
costflow();
printf("%d\n", ans);
}
return 0;
}
分享到:
相关推荐
从入门到精通:最小费用流的“zkw算法”.doc
图论- 网络流- 费用流- zkw 费用流.rar
【项目资源】: 包含前端、后端、移动开发、操作系统、人工智能、物联网、信息化管理、数据库、硬件开发...有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。
部分源码 #include "deploy.h" #include "lib_io.h" #include "lib_time.h" #include "stdio.h" int main(int argc, char *argv[]) { print_time("Begin"); char *topo[MAX_EDGE_NUM];... line_num = read_file(topo...
大神提供的最小成本流的简便算法,给大家进行参考,希望有所收获
ZKW费用流模板,测试好用,不易被卡,比赛专用
最小费用最大流(spfa增广,zkw费用流) spfa 增广 zkw费用流 上下界最大流 上下界最小费用最大流 无源无汇可行流 无源无汇最小费用可行流 字符串 KMP 扩展KMP Manacher回文子串 字符串最小表示 其它 树的hash 梭哈...
zkw线段树模板类,可动态统计区间最大值。代码略作修改即可动态统计区间和
ZKW线段树的实现源码-pascal版,可保证其正确性并在logN时间复杂度类进行区间操作
【zkw线段树讲稿】统计的力量-线段树.pdf
餐巾问题 Meno:Zkw 最小费用最大流 */ #include using namespace std; const int Maxn=2005,oo=0x7fffffff/2; struct Edge{int to,next,op,vol,cost;}w[Maxn*100];
传说中的ZKW线段树 比一般线段树快 ...与一般的二叉搜索树不同的是,线段树保存的是所有元素可能取的值,而不是每个元素。通常情况下,线段树只用叶节点表示每个值。而其余的节点对应的就是一个范围。
线段树
百度地图API、轮播图以及瀑布流。外带一个登陆界面(不带后台),账号zkw299,密123456
|初赛 | cdn1 |赛区第32,前36进入复赛| 赛题如表前所述 |先用dijkstra算法求粗糙解,再用最小费用最大流求精确解| |复赛 | cdn2 |赛区第3,前4进入总决赛|1)服务器具有10个等级的输出能力 2)节点有部署费用|1) ...
GPS库
统计的力量-zkw线段树 zkw的讲课ppt,线段树经典之作,内含一种采用堆式存储的zkw线段树及其使用方法
B 的约数之和对 MOD 取模 . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.13 莫比乌斯反演 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.13.1 莫比乌斯函数 . . . ...
中科微北斗 GPS android驱动 ATGM332D ATGM336H驱动 适用于Android 7系统