382. K取方格数(图论,费用流,拆点,上下界可行流,网格图模型)

这篇具有很好参考价值的文章主要介绍了382. K取方格数(图论,费用流,拆点,上下界可行流,网格图模型)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

在一个 N×N 的矩形网格中,每个格子里都写着一个非负整数。

可以从左上角到右下角安排 K 条路线,每一步只能往下或往右,沿途经过的格子中的整数会被取走。

若多条路线重复经过一个格子,只取一次。

求能取得的整数的和最大是多少。

输入格式

第一行包含两个整数 N 和 K。

接下来 N 行,每行包含 N 个不超过 1000 的整数,用来描述整个矩形网格。

输出格式

输出一个整数,表示能取得的最大和。

数据范围

1≤N≤50,
0≤K≤10

输入样例:
3 2
1 2 3
0 2 1
1 4 2
输出样例:
15

解析: 

本题我们需要在一个 n×n 的矩阵,每个格子上都写着一个非负整数,我们指定 k 条路线,每一步只能往下或往右,每个格子上的数只能取一次,求如何指定这 k 条路线,能让取得的整数和最大。

像这种方格取数问题,存在简单版本,如指定一条路线或两条路线的问题,可以使用线性 dp 来求,但是本题由于最多会有 10 条路径,用 dp 会超时,所以这里考虑用费用流来解决。

首先我们先不去考虑每个格子只能取一次的问题,我们先设法将路线转化成流。起点是左上角,终点是右下角,所有的路线都是从左上角走到右下角。所以我们可以建立一个源点和一个汇点,从源点向左上角连一条容量为 k 的边,从汇点向右下角连一条容量为 k 的边,表示有 k 条路线从左上角走到右下角。然后每个格子都可以向右和向下走,因此从每个格子向右和向下两个格子连边,且每个格子能走多次,没有限制,因此这些边的容量都是 +∞。这样我们就在网格图上建立了一个流网络。

此时可以发现流网络的任意一个可行流和原问题的任意一个方案都是一一对应的。并且原问题的每一个方案都一定有 k 条路线,所以在流网络中对应的可行流一定都是满流。这个比较直观,可以自行证明。

现在回到原题,我们要从所有路线中找出总价值最大的 k 条路线,也就是说我们要在流网络中所有的最大可行流里面找到一个费用最大的方案。那么我们就需要考虑如何将费用结合到流网络里面。

可以发现,本题的所有费用都是在格子上(点上)的,所以我们可以用拆点技巧把每个点拆成入点和出点,然后从每个入点向对应的出点连一条边,费用是该点的价值。

但是这里还有一个限制,就是每个点的价值我们都只能取走一次,以后的若干次再走到这个点上都不会在获得价值。因此我们可以对应这两种情况来建立两条边。对于每个点,从入点向出点连一条容量是 1,费用是该点价值的边,再连一条容量是 +∞,费用是 0 的边。这样我们每次走到一个点,只能走一次有费用的边来获取价值,之后的几次都只能走没有费用的边,保证每个点的价值只能取走一次。

这样本题的流网络就构建完成了,并且原问题的任意一组走法都能对应到流网络中的任意一个满流,原问题任意一组走法走过的价值之和都能对应到流网络中任意一个满流的费用。因此我们想求原问题的最大价值,等价于求流网络的最大费用最大流。文章来源地址https://www.toymoban.com/news/detail-861345.html

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 50*50*2+10, M = (N*4) * 2 + 10, INF = 0x3f3f3f3f;
int n, m,K, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];

void add(int a, int b, int c, int d) {
	e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx++;
	e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx++;
}

int get(int a, int b, int c) {
	return ((a - 1) * n + b)*2 + c;
}

bool spfa() {
	int hh = 0, tt = 1;
	memset(d, -0x3f, sizeof d);
	memset(incf, 0, sizeof incf);
	q[0] = S, d[S] = 0, incf[S] = 0x3f;
	while (hh != tt) {
		int t = q[hh++];
		if (hh == N)hh = 0;
		st[t] = 0;
		for (int i = h[t]; i != -1; i = ne[i]) {
			int j = e[i];
			if (d[j] < d[t] + w[i] && f[i]) {
				d[j] = d[t] + w[i];
				pre[j] = i;
				incf[j] = min(incf[t], f[i]);
				if (!st[j]) {
					st[j] = 1;
					q[tt++] = j;
					if (tt == N)tt = 0;
				}
			}
		}
	}
	return incf[T] > 0;
}

int EK() {
	int cost = 0;
	while (spfa()) {
		int t = incf[T];
		cost += t * d[T];
		for (int i = T; i != S; i = e[pre[i] ^ 1]) {
			f[pre[i]] -= t;
			f[pre[i] ^ 1] += t;
		}
	}
	return cost;
}

int main() {
	cin >> n >> K;
	memset(h, -1, sizeof h);
	S = 2 * n * n + 2, T = S + 1;
	add(S, get(1, 1, 0), K, 0);
	add(get(n, n, 1), T, K, 0);
	for (int i = 1; i <= n; i++) {
		for (int j = 1, a; j <= n; j++) {
			scanf("%d", &a);
			add(get(i, j, 0), get(i, j, 1), 1, a);
			add(get(i, j, 0), get(i, j, 1), INF, 0);
			if (i < n)add(get(i, j, 1), get(i + 1, j, 0), INF, 0);
			if (j < n)add(get(i, j, 1), get(i, j + 1, 0), INF, 0);
		}
	}
	printf("%d\n", EK());
	return 0;
}

到了这里,关于382. K取方格数(图论,费用流,拆点,上下界可行流,网格图模型)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划之二维费用的背包模型

    前置知识: 01背包问题:动态规划之01背包模型_如何何何的博客-CSDN博客 完全背包问题:动态规划之完全背包模型_如何何何的博客-CSDN博客 多重背包问题:动态规划之多重背包模型_如何何何的博客-CSDN博客 二维费用即背包问题有两个限制条件。 例题: 有 N 件物品和一个容

    2024年02月15日
    浏览(11)
  • 缓解大语言模型(LLM)幻觉的可行方法探究(课程综述)

    摘要 :2022年11月OpenAI推出能够进行多场景对话的大语言模型ChatGPT,ChatGPT凭借大规模的训练参数、海量的训练数据及强化学习人类反馈在语义理解、语言生成、机器翻译、知识科普、程序编辑等多个方面获得了巨大成功,引发了新的技术浪潮。但由于模型训练数据缺乏时效性

    2024年01月16日
    浏览(16)
  • 轻松白嫖GPT-4,已经标星38K,不再害怕高昂的AI模型费用!

    计算机专业学生@xtekky在GitHub上发布了一个名为gpt4free的开源项目,该项目允许您免费使用GPT4和GPT3.5模型。这个项目目前已经获得了380000颗星。 开源地址:https://github.com/xtekky/gpt4free 简而言之,该项目通过劫持已接入GPT-4 API的其他网站(如Bing、forefront等)并利用逆向工程技术

    2024年02月07日
    浏览(26)
  • 涌现出来的模拟能力#OpenAI视频生成大模型构建世界模拟器的可行性

    Q:Sora出来后,普通人应该怎么办?  \\\"Sora的到来带来了机遇和挑战。普通人关注创意和技术,探索表达想法的新方式。🌟🔬他们制作高质量视频,平衡工作与生活,并拥抱行业变革。梦想成为现实。💡🎥👥#SoraRevolution\\\" 今天一早被OpenAI的视频生成刷屏了。社交媒体上,开

    2024年02月19日
    浏览(20)
  • OpenGL加载模型 之网格

    我们的工作就是去解析这些导出的模型文件,并将其中的模型数据存储为OpenGL能够使用的数据。一个常见的问题是,导出的模型文件通常有几十种格式,不同的工具会根据不同的文件协议把模型数据导出到不同格式的模型文件中。 有的模型文件格式只包含模型的静态形状数据

    2024年02月03日
    浏览(8)
  • 动网格模型算法基础(二)

    本贴主要简述动网格模型算法 FLUENT动网格模型能够根据用户指定的边界运动、网络类型和网格再生方式自动地调节内部体网格节点的位置。 体网格的再生; 边界运动或变形的指定; (一)铺层(Layering) 铺层包括边界上网格的生成和消失,该算法会根据计算区域的扩张或收

    2024年02月07日
    浏览(3)
  • 模型服务网格:云原生下的模型服务管理

    模型服务网格(Model Service Mesh)是一种架构模式,用于在分布式环境中部署和管理机器学习模型服务。它提供了一个可扩展的、高性能的基础架构,用于将多个模型服务进行管理、部署和调度,以此更好地处理模型的部署、版本管理、路由和推理请求的负载均衡。 模型服务网

    2024年02月04日
    浏览(11)
  • LiblibAI哩布哩布AI:满血不收费的ai生图真的来了!过万授权模型免费用!

    LiblibAI, 中文名:哩布哩布AI是原创AI模型分享社区,这里有最新、最热门的模型素材, 10万+模型免费下载 。你可以在这里分享优秀的作品,与中国原创模型作者交流,共同探索AI绘画。 访问地址放在文章结尾,大家自取。 Liblibai免费吗? liblibai每日登录后会送算力值: 1.非会员每

    2024年04月25日
    浏览(10)
  • 从有限元到Unity——从abaqus网格模型文件到Unity模型数据

    一、从有限元到Unity——有限元网格信息导出及分析 二、从有限元到Unity——Unity网格编程 三、从有限元到Unity——从abaqus网格模型文件到Unity模型数据 四、从有限元到Unity——有限元分析结果导出 五、从有限元到Unity——渲染管线与着色器   上一篇文章大概说了Unity的网格

    2024年02月03日
    浏览(14)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包