POJ 3422 最小费用最大流 zkw或者普通版本

2023-11-08 08:58

本文主要是介绍POJ 3422 最小费用最大流 zkw或者普通版本,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

建图的话

每个点拆成两个点u, u',连一条容量为1费用为金币数的边,再连一条容量为k,费用为0的边

然后每个点和他右边或者下边的点连边 i'->j这样连

然后源点连1点,右下角那个点去连汇点,容量都为k,费用为0

普通写法

#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;
}


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 5555
#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, k;
int main()
{int w;while(scanf("%d%d", &nt, &k) != EOF){init();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);costflow();printf("%d\n", -ans);}return 0;
}


这篇关于POJ 3422 最小费用最大流 zkw或者普通版本的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/368903

相关文章

Linux卸载自带jdk并安装新jdk版本的图文教程

《Linux卸载自带jdk并安装新jdk版本的图文教程》在Linux系统中,有时需要卸载预装的OpenJDK并安装特定版本的JDK,例如JDK1.8,所以本文给大家详细介绍了Linux卸载自带jdk并... 目录Ⅰ、卸载自带jdkⅡ、安装新版jdkⅠ、卸载自带jdk1、输入命令查看旧jdkrpm -qa

Tomcat版本与Java版本的关系及说明

《Tomcat版本与Java版本的关系及说明》:本文主要介绍Tomcat版本与Java版本的关系及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat版本与Java版本的关系Tomcat历史版本对应的Java版本Tomcat支持哪些版本的pythonJ

IDEA中Git版本回退的两种实现方案

《IDEA中Git版本回退的两种实现方案》作为开发者,代码版本回退是日常高频操作,IntelliJIDEA集成了强大的Git工具链,但面对reset和revert两种核心回退方案,许多开发者仍存在选择... 目录一、版本回退前置知识二、Reset方案:整体改写历史1、IDEA图形化操作(推荐)1.1、查看提

JDK多版本共存并自由切换的操作指南(本文为JDK8和JDK17)

《JDK多版本共存并自由切换的操作指南(本文为JDK8和JDK17)》本文介绍了如何在Windows系统上配置多版本JDK(以JDK8和JDK17为例),并通过图文结合的方式给大家讲解了详细步骤,具有... 目录第一步 下载安装JDK第二步 配置环境变量第三步 切换JDK版本并验证可能遇到的问题前提:公司常

nvm如何切换与管理node版本

《nvm如何切换与管理node版本》:本文主要介绍nvm如何切换与管理node版本问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录nvm切换与管理node版本nvm安装nvm常用命令总结nvm切换与管理node版本nvm适用于多项目同时开发,然后项目适配no

Mybatis从3.4.0版本到3.5.7版本的迭代方法实现

《Mybatis从3.4.0版本到3.5.7版本的迭代方法实现》本文主要介绍了Mybatis从3.4.0版本到3.5.7版本的迭代方法实现,包括主要的功能增强、不兼容的更改和修复的错误,具有一定的参考... 目录一、3.4.01、主要的功能增强2、selectCursor example3、不兼容的更改二、

pytorch+torchvision+python版本对应及环境安装

《pytorch+torchvision+python版本对应及环境安装》本文主要介绍了pytorch+torchvision+python版本对应及环境安装,安装过程中需要注意Numpy版本的降级,... 目录一、版本对应二、安装命令(pip)1. 版本2. 安装全过程3. 命令相关解释参考文章一、版本对

springboot3.4和mybatis plus的版本问题的解决

《springboot3.4和mybatisplus的版本问题的解决》本文主要介绍了springboot3.4和mybatisplus的版本问题的解决,主要由于SpringBoot3.4与MyBat... 报错1:spring-boot-starter/3.4.0/spring-boot-starter-

mac安装nvm(node.js)多版本管理实践步骤

《mac安装nvm(node.js)多版本管理实践步骤》:本文主要介绍mac安装nvm(node.js)多版本管理的相关资料,NVM是一个用于管理多个Node.js版本的命令行工具,它允许开发者在... 目录NVM功能简介MAC安装实践一、下载nvm二、安装nvm三、安装node.js总结NVM功能简介N

java中不同版本JSONObject区别小结

《java中不同版本JSONObject区别小结》本文主要介绍了java中不同版本JSONObject区别小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1. FastjsON2. Jackson3. Gson4. org.json6. 总结在Jav