首页 > 其他分享 >网络流&费用流&二分图

网络流&费用流&二分图

时间:2024-10-29 19:22:24浏览次数:3  
标签:二分 费用 匹配 最大 曼哈顿 子图 网络 权值

NOIP 也许考不到,但是可以拿来骗分也说不定(

算法原理就算了,反正也不需要知道,只需要知道它在干什么并且会建图就行了。

二分图就是左右两部点,同一部内的点无连边,可以考虑建二分图后网络流。

持续放些题。

一些基本理论和建模方式

  • 最小割=最大流

  • 最大权闭合子图

  • 切糕模型

  • 二分图最小点覆盖=最大匹配数

  • 二分图最大独立集=二分图的总顶点数-最大匹配数

  • 最小路径覆盖数=DAG中的点数-二分图最大匹配数(在DAG中选取最少的路径,使每个点仅属于一条路径且路径不可重复)(将每个点拆开,边表示为一个点的出度到另一个点的入度,点拆开的两个部分分属两部)

P3410 拍照

你需要知道什么是最大权闭合子图,即给定一张有向图,每个点都有一个权值(可以为正或负或 \(0\)),你需要选择一个权值和最大的子图,使得子图中每个点的后继都在子图中。

做法:考虑网络流,若 \(u\) 节点权值非负,\(s\) 向 \(u\) 连一条流量为 \(val[u]\) 的边,权值为负则 \(u\) 向 \(t\) 连一条流量为 \(|val[u]|\) 的边。原图上的边流量为 \(\inf\),所有正权值减去最小割即是答案,这是板子题,证明懒得证。

[AGC034D] Manhattan Max Matching

不管曼哈顿距离,容易看出这是二分图,暴力 \(O(n^2)\) 连边后也显然是跑二分图最大权匹配。考虑费用流来做,要建源点 \(s\) 向所有左部点连容量 \(1\) 边权 \(0\) 的边,所有右部点也这么向汇点 \(t\) 连边。

考虑优化建图。关于曼哈顿距离的最大值有个trick了:考虑拆绝对值,这样曼哈顿距离的四个坐标取值都有正负号的取值,共16种曼哈顿距离的式子。我们要暴力全部连边的原因是不能简化曼哈顿距离的形式让所有点可以连在固定的几个点上计算。现在可以了,考虑建四个点,让 左部点向这四个点/这四个点向右部点 连一条容量 \(inf\) 权值为 \(\pm x_i\pm y_i\) 的边,然后直接跑最大费用最大流就行,这个题保证了两部点的数量相同且要匹配完。需要注意的是本题中曼哈顿距离拆式子的trick不能用在最小值上。

标签:二分,费用,匹配,最大,曼哈顿,子图,网络,权值
From: https://www.cnblogs.com/heshuwan/p/18514211

相关文章

  • 16.网工入门篇--------介绍下网络服务及应用
    一、网络服务的概念网络服务是指通过网络提供的软件功能或设施,它允许不同的设备和用户在网络环境中进行信息交换、资源共享和协作。这些服务基于各种网络协议,以实现高效、可靠的通信。二、常见网络服务类型(一)文件传输服务FTP(文件传输协议)原理:FTP是一种用于在网络上进......
  • 明星人脸识别基于VGG、MTCNN、RESNET深度学习卷积神经网络应用|附数据代码
    全文链接:https://tecdat.cn/?p=38046原文出处:拓端数据部落公众号分析师:XinzuDu 人脸识别技术作为生物特征识别技术的重要组成部分,在近三十年里得到了广泛的关注和研究,已经成为计算机视觉、模式识别领域的研究热点。然而由于存在光线、背景、人脸遮挡等问题,如何准确识别出人......
  • 100个网络知识,懂一半绝对高手
    1)什么是链接?链接是指两个设备之间的连接。它包括用于一个设备能够与另一个设备通信的电缆类型和协议。2)OSI参考模型的层次是什么?有7个OSI层:物理层,数据链路层,网络层,传输层,会话层,表示层和应用层。3)什么是骨干网?骨干网络是集中的基础设施,旨在将不同的路由和数据......
  • 卷积神经网络和深度神经网络的区别是什么
    卷积神经网络和深度神经网络的区别主要体现在:1.结构形式不同;2.适用场景不同;3.参数数量不同;4.信息处理方式不同;5.对数据的要求不同。总的来说,卷积神经网络在图像处理等领域有特别优势,能有效提取局部特征;而深度神经网络是一种通用的神经网络结构,适用于多种复杂的预测和分类问题。......
  • VMware虚拟机上的Ubuntu网络故障仍需要下载文件的共享文件夹解决办法
    有时候虚拟机的网络问题就像一个阴晴不定的女孩一样,昨天还畅所欲言今天却突然掉线,但是我们仍需要下载一些文件、工具或者源码用来测试,那么这个方法仅适用于这种不需要解决网络问题的特殊情况(有能力还是要去解决网络问题)首先要在计算机上下载你所需要的文件,然后复制到虚拟机上......
  • 多品牌NVR管理工具/设备EasyNVR多个NVR同时管理实现监控网络高效整合
    随着科技的飞速进步,监控视频在各行各业中的应用变得愈发广泛。为了更好地管理和运用这些宝贵的视频资源,对视频进行联网与整合的需求也随之增加。视频联网技术通过汇聚不同地理位置和设备的视频资源,实现了实时的资源共享与集中化管控。在公共安全、交通监控、商业安防等多个领域......
  • 贝叶斯网络应用在哪些方面
    贝叶斯网络是一种强大的统计工具,用于表示随机变量之间的依赖关系。它的应用非常广泛,包括1、医疗诊断和疾病预测;2、风险管理和金融建模;3、机器学习和人工智能。其中,在医疗领域,贝叶斯网络可用于分析疾病的潜在原因,并预测病人的恢复概率。一、医疗诊断和疾病预测疾病分析:通过收......
  • C++ 网络编程 IO多路复用、select、poll、epoll知识点总结
    1.什么是I/O多路复用?I/O多路复用(I/OMultiplexing)是一种编程技术,允许一个线程或进程同时管理多个I/O通道(如文件描述符、套接字等)。它使得单个进程能够在不使用多个线程或进程的情况下,同时处理多个I/O操作。这在网络编程和高性能服务器中尤为重要,因为它可以有效地利用系......
  • Pytorch学习--神经网络--非线性激活
    一、用法torch.nn.ReLU图像处理中的应用:在图像处理任务中,ReLU激活函数能够增强特征提取的能力,使网络更好地捕捉图像的细节和边缘。这是因为ReLU对大部分负数响应为零,能在一定程度上减少网络计算量,并对特征层起到稀疏化的效果,避免信息的过度平滑。torch.nn.Sigmoid......
  • 在C语言中进行网络编程时,有哪些辅助工具可用
    标题:在C语言中进行网络编程时,有哪些辅助工具可用?在C语言中进行网络编程时,可用的辅助工具包括套接字库(如Winsock、BSDSockets)、协议库(如OpenSSL)、网络调试工具(如Wireshark)、以及集成开发环境(如Eclipse、VisualStudio)。这些工具为开发者提供了强大的支持,使得在C语言中进行网络编......