首页 > 其他分享 >网络流建图汇总

网络流建图汇总

时间:2024-11-05 11:08:48浏览次数:4  
标签:可行 源点 汇总 网络 最小 流建图 下界 汇上 割掉

Dining G

一个点有两重限制,将点放中间,两边分别放两个限制,中间点点拆点连 1 表示限制

CTSC1999 家园 / 星际转移问题

时间限制可以分层图,分层图不需二分,直接一层层建即可

企鹅游行

这种有限制的拆点就完了。

时序问题按照时间建即可。

一般出现调整的可以考虑把调整的看成流量

P1345 奶牛的电信Telecowmunication

删点可以拆点后两点之间连 1 边


花费最少->最小割(割掉一条边相当于选)

收益最大->总权值减最小割 (割掉一条边相当于不选)

【例题1】任务分配

[P2057 SHOI2007] 善意的投票 / [JLOI2010] 冠军调查

花费最少,即最小割

如何满足两点选择不同就加代价?

向两点之间连双向边即可。

P1361 小M的作物

花费最大,总代价减最小割。

两点(多点)相同有贡献。

若割掉 \(1,2\) ,则 \(c_1\) 也需要割(否则割掉 \(3,4,c_2\) ,那就不需要割 \(1,2\) 了)

\(3,4\) 同理

若选择 \(1,4/2,3\) ,则 \(c_1,c_2\) 都割掉

P4126 AHOI2009 最小割

最小割集:残余网络上从S出发bfs,连接被S标记的点和未被S标记的点即为割边。

找最小割必须边:

  1. 从S开始BFS跑残量网络。
  2. 从T开始反向BFS跑残量网络。
  3. 枚举从S指向T的满流边,这些边即为必须边

找最小割可行边:

  1. 满流

  2. 删掉后找不到u -> v的路径

    残余网络中 tarjan 跑 SCC, \((u, v)\) 的 \(u, v\) 都在同一 SCC 中说明存在残量网络 \(u \to v\)的路径


多源汇最大流:超级源点向每个源点连 \(inf\),汇点同理


无源汇上下界可行流:

先让所有边都为 \(l\) ,处理每个点入流量-出流量。

\(x > 0\) ,源点向 \(u\) 连 \(x\) ,相当于需要源点帮助流入

\(x < 0\) ,\(u\) 向汇点连 \(-x\) ,相当于需要汇点帮助流出

判断最大流是否等于源点连边。即是否满流

有源汇上下界可行流:

源点 \(t\) 向 \(s\) 流 \([0,inf]\) 平衡流量即可。

此时这条边的流量即为可行流时流量。

有源汇上下界最大流:

跑完可行流再跑一遍,相加。

有源汇上下界最小流:

跑完可行流再跑 \(t\) 到 \(s\) 最大流,相减。


最大权闭合子图:

一张有向无环图,点有点权(可能为负),对于边 \((u,v)\),如果选择 \(u\) ,就必须选择 \(v\)。求所选的点的最大权值和。

点权为正,连 \((s,u,w)\) ,相当于放弃正点

点权为负,连 \((u,t,-w)\) ,相当于选择负点

其他边连 \((u,v,inf)\)

答案为正权点和-最小割

P2805 NOI2009 植物大战僵尸

P4174 NOI2006 最大获利


费用流:

注意dfs时的vis。

若有负代价环可以先强制费用为负的边满流,跑上下界有源汇费用流即可

NOI2008 志愿者招募

NOI 2008 志愿者招募 employee (byvoid.com)

线性规划建图。

标签:可行,源点,汇总,网络,最小,流建图,下界,汇上,割掉
From: https://www.cnblogs.com/Anonymely/p/18527499

相关文章

  • python 实现灰色模型神经网络拟合算法
    灰色模型神经网络拟合算法介绍灰色模型神经网络拟合算法结合了灰色预测模型和神经网络的优势,用于处理样本数据量较少、信息不完全或具有不确定性的系统预测问题。以下是对该算法及其原理的详细介绍:一、灰色预测模型(GrayForecastModel)灰色预测是对既含有已知信息又含有......
  • 基于卷积神经网络的大豆病虫害识别与防治系统,resnet50,mobilenet模型【pytorch框架+pyt
     更多目标检测和图像分类识别项目可看我主页其他文章功能演示:大豆病虫害识别与防治系统,卷积神经网络,resnet50,mobilenet【pytorch框架,python源码】_哔哩哔哩_bilibili(一)简介基于卷积神经网络的大豆病虫害识别与防治系统是在pytorch框架下实现的,这是一个完整的项目,包括代码,......
  • 强化学习理论-第0课-汇总
    ......
  • Unity网络通信(part1.通信方案概述)
    目录前言弱联网和强联网游戏弱联网游戏强联网游戏长连接和短连接游戏短连接游戏长连接游戏Socket、HTTP、FTPSocketHttp/HttpsFTP总结前言        网络通信是服务器与Unity应用程序之间进行数据交换和通信的过程,这种通信在游戏开发、实时数据同步、多......
  • Unity网络通信(part2.通信必备知识)
    目录前言IPAddress类IPEndPoint类域名解析IPHostEntry类Dns类异步方法异步编程的好处注意事项前言        我们知道想要进行网络通信,进行网络连接,首先我们需要找到对应设备,IP和端口号是定位网络中设备必不可少的关键元素。C#中提供了对应的IP和端口相关的......
  • 学习网络安全的良好习惯
    在学习网络安全过程中,养成以下良好习惯有助于提升学习效果:一、知识学习习惯1.系统学习基础理论   深入理解网络协议是非常关键的。例如,透彻掌握TCP/IP协议族,包括IP地址的分类、子网掩码的计算、TCP和UDP协议的区别等。以TCP的三次握手为例,这是建立可靠连接的基础过程......
  • 知识点:计算机网络的OSI七层模型中的数据链路层的功能和设备
    知识点:该题目考察的知识点是计算机网络的OSI七层模型中的数据链路层的功能和设备。在OSI模型中,数据链路层是第二层,它负责在相邻的网络设备之间传输帧,并且确保帧的可靠传输。数据链路层的主要功能包括帧同步、差错控制、流量控制以及物理寻址。相关知识点内容:OSI七层模型:国际标......
  • 20222323 2024-2025-1 《网络与系统攻防技术》实验四实验报告
    1.实验内容一、恶意代码文件类型标识、脱壳与字符串提取对提供的rada恶意代码样本,进行文件类型识别,脱壳与字符串提取,以获得rada恶意代码的编写作者,具体操作如下:(1)使用文件格式和类型识别工具,给出rada恶意代码样本的文件格式、运行平台和加壳工具;(2)使用超级巡警脱壳机等脱壳软件,......
  • 【eNSP】企业网络架构实验
    一、实验目的1、熟练掌握交换机的基本配置命令2、熟练掌握vlan原理3、熟练掌握交换机端口模式二、实验内容需求:根据要求利用现有实验设备组建小型局域网三、实验设备1、交换机S3700×4台;2、个人PC×3台;3、服务器×3台;四、实验要求1、将7台PC设备划分为市场部2......