没有合适的资源？快使用搜索试试~ 我知道了~

文库首页开发技术其它7[1].胡伯涛《最小割模型在信息学竞赛中的应用》

7[1].胡伯涛《最小割模型在信息学竞赛中的应用》

5星 · 超过95%的资源需积分: 10 18 下载量 54 浏览量 2011-08-30 15:24:28 上传评论收藏 682KB PPT 举报

温馨提示

试读

37页

最小割模型在信息学竞赛中的应用 Applications of Minimum Cut Modelin Informatics

资源推荐

资源详情

资源评论

最小割模型

在信息学竞赛中的应用

Applications of Minimum Cut Mod

in Informatics

胡伯涛 Amber

[ADN.cn]

福州第一中学 Fuzhou No.1 Middle School

▪

两个部分

1.最大权闭合图

标准解答的一个更一般化的扩展模型

2.改进算法

达到用最大流解决该问题的理论下界

引入

NOI 2006 最大获利

▪

最小割是最大流的对偶问题。

不直观，模型隐蔽。

▪

展示最小割模型应用的巧妙构图方法和独

特思维方式

网络流首次进入 NOI

NOI 2006 最大获利 (Profit)

问题描述

简要描述

▪

有 n 个结点， m 条无向边可供建设。

▪

建立一个结点 u 有一定的花费 p

。建立一

条无向边有一定的非负收益 w

e 。

▪

建立一条无向边 (u, v ) 的必要条件是要先建

立点 u ，点 v 。

▪

求最大获利。

NOI 2006 最大获利 (Profit)

分析

▪

目的：选出一个边集 E’, 点集 V’ 。且最大

化：

▪

限制条件：对于在 E’ 中每条边 (u, v) ，它的

端点 u ， v 一定要在 V’ 中。

提出解决事件依赖关系的有力图论工具：闭合图。

必要条件

' '

Maximize

e v

e E v V

w p

 



 

边

依赖

点

最大权闭合图

定义

▪

有向图的闭合图（ clos

ure ）：

闭合图内任意点的任意

后继也一定还在闭合图

中。

▪

物理意义

事物间依赖关系：一个事

件要发生，它需要的所有

前提也都一定要发生。

▪

最大权闭合图是点权之

和最大的闭合图。

其中 {3, 4, 5} 是一个闭合图。 3 的

后继 4 ， 4 的后继 5 ，都在闭合图

中。

1 2

3 4

-6

-3

而 {1, 4, 5} 不是一个闭合图，因为

点 2 是点 1 的后继，但不在闭合图

中。

剩余36页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

BigBen_PigBear

2013-06-04

很好的东西，谢谢分享

lz9506

粉丝: 0
资源: 1

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

7[1].胡伯涛《最小割模型在信息学竞赛中的应用》

最小割模型在信息学竞赛中的应用

7.胡伯涛《最小割模型在信息学竞赛中的应用》2

最小割在信息学竞赛中的应用

7.胡伯涛《最小割模型在信息学竞赛中的应用》.ppt

总结信息学竞赛中并查集的拓展应用

部分贪心在信息学竞赛中的应用1

acm国家集训队2007年论文合集

国家集训队2007论文集

IOI国家集训队论文集1999-2019

图论知识总结

最大流在信息学竞赛中应用的一个模型

RMQ在信息学竞赛中的应用(1)

随机化算法在信息学竞赛中的应用1

浅析二分图匹配在信息学竞赛中的应用

隐马尔可夫模型在生物信息学中的应用

论C++语言在信息学竞赛中的应用 论C++语言在信息学竞赛中的应用

C++在信息学竞赛中应用

贝叶斯模型在生物信息学中一种应用

浅析字母树在信息学竞赛中的应用.pdf

RMQ在信息学竞赛中的应用

浅析字母树在信息学竞赛中的应用

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

NPPJSONViewer.zip

GD32替换STM32注意事项.pdf

最新资源

论C++语言在信息学竞赛中的应用论C++语言在信息学竞赛中的应用

Qt 5实现串口调试助手（源工程文件、0积分下载）