POJ 3422 Kaka's Matrix Travels(费用流)
amp 39 poj 费用 matrix
2023-09-27 14:27:02 时间
POJ 3422 Kaka's Matrix Travels
题意:一个矩阵。从左上角往右下角走k趟,每次走过数字就变成0,而且获得这个数字,要求走完之后,所获得数字之和最大
思路:有点类似区间k覆盖的建图方法,把点拆了,每一个点有值的仅仅能选一次,其它都是无值的。利用费用流,入点出点之间连一条容量1,有费用的边,和一条容量k - 1,费用0的边,然后其它就每一个点和右边和下边2个点连边。然后跑费用流
代码:
#include <cstdio> #include <cstring> #include <vector> #include <queue> #include <algorithm> using namespace std; const int MAXNODE = 5005; const int MAXEDGE = 100005; typedef int Type; const Type INF = 0x3f3f3f3f; struct Edge { int u, v; Type cap, flow, cost; Edge() {} Edge(int u, int v, Type cap, Type flow, Type cost) { this->u = u; this->v = v; this->cap = cap; this->flow = flow; this->cost = cost; } }; struct MCFC { int n, m, s, t; Edge edges[MAXEDGE]; int first[MAXNODE]; int next[MAXEDGE]; int inq[MAXNODE]; Type d[MAXNODE]; int p[MAXNODE]; Type a[MAXNODE]; void init(int n) { this->n = n; memset(first, -1, sizeof(first)); m = 0; } void add_Edge(int u, int v, Type cap, Type cost) { edges[m] = Edge(u, v, cap, 0, cost); next[m] = first[u]; first[u] = m++; edges[m] = Edge(v, u, 0, 0, -cost); next[m] = first[v]; first[v] = m++; } bool bellmanford(int s, int t, Type &flow, Type &cost) { for (int i = 0; i < n; i++) d[i] = INF; memset(inq, false, sizeof(inq)); d[s] = 0; inq[s] = true; p[s] = s; a[s] = INF; queue<int> Q; Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = false; for (int i = first[u]; i != -1; i = next[i]) { Edge& e = edges[i]; if (e.cap > e.flow && d[e.v] > d[u] + e.cost) { d[e.v] = d[u] + e.cost; p[e.v] = i; a[e.v] = min(a[u], e.cap - e.flow); if (!inq[e.v]) {Q.push(e.v); inq[e.v] = true;} } } } if (d[t] == INF) return false; flow += a[t]; cost += d[t] * a[t]; int u = t; while (u != s) { edges[p[u]].flow += a[t]; edges[p[u]^1].flow -= a[t]; u = edges[p[u]].u; } return true; } Type Mincost(int s, int t) { Type flow = 0, cost = 0; while (bellmanford(s, t, flow, cost)); return cost; } } gao; const int N = 55; const int d[2][2] = {0, 1, 1, 0}; int n, k, g[N][N]; int main() { while (~scanf("%d%d", &n, &k)) { gao.init(n * n * 2); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { scanf("%d", &g[i][j]); gao.add_Edge(i * n + j, i * n + j + n * n, k - 1, 0); gao.add_Edge(i * n + j, i * n + j + n * n, 1, -g[i][j]); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int a = 0; a < 2; a++) { int x = i + d[a][0]; int y = j + d[a][1]; if (x < 0 || x >= n || y < 0 || y >= n) continue; int u = i * n + j, v = x * n + y; gao.add_Edge(u + n * n, v, k - 1, 0); } } } printf("%d\n", -gao.Mincost(0, n * n * 2 - 1)); } return 0; }
版权声明:本文博客原创文章,博客,未经同意,不得转载。
相关文章
- Unity【Bounds & Vector3 Cross】- 如何判断一个物体是否在一个凸边体三维区域内
- PyTorch的自动混合精度(AMP)
- windows server服务器启动tomcat后控制台总是卡住,接口拿不到数据,导致系统无法访问,需要按ctrl+c系统才能继续运行 & tomcat的"ctrl + c" 问题(启动假死状态)
- Asp.Net_Linq To Sql 语法 子查询 & In & Join
- Smart Forms&ScriptFrom
- 月薪20k的性能测试必备技能:发现性能瓶颈&掌握性能调优
- centos 安装mysql时错误unknown variable 'defaults-file=/opt/redmine-2.6.0-2/mysql/my.cnf'
- POJ 2480 Longge's problem 积性函数
- HTML & CSS – Responsive Image 响应式图片 (完整版)
- Beat 'Em Up Game Starter Kit (横版格斗游戏) cocos2d-x游戏源代码
- hdu 2732 && poj 2711 Leapin' Lizards(dinic && 拆点建图经典)
- json包中的Marshal&Unmarshal 文档译本
- XHXJ's LIS HDU - 4352 最长递增序列&数位dp
- 【Python21天学习挑战赛】集合 & 数据类型补充
- HDU 3966 Aragorn's Story(树链剖分)
- iOS 面试题:OC标题的基本概念<延续>
- hdu2852--KiKi's K-Number(段树,求第一k的数量)
- UVA11038- How Many O's?(组合数学)
- 条件判断 && 逻辑运算符
- Pipe Isometric Drawing Development – Math Functions
- Python 【精】AttributeError: 'Module' object has no attribute 'STARTF_USESHOWINDOW'
- javascript&nbsp;冒泡排序法
- 我的Android进阶之旅------>解决Error:Could not find property 'compile' on org.gradle.api.internal.artifacts.
- 我的Android进阶之旅------>解决:debug-stripped.ap_' specified for property 'resourceFile' does not exist.
- 我的Android进阶之旅------>Android中MediaButtonReceiver广播监听器的机制分析
- 我的Java开发学习之旅------>Java多线程下载文件 实例