博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【BZOJ】1585: [Usaco2009 Mar]Earthquake Damage 2 地震伤害
阅读量:6540 次
发布时间:2019-06-24

本文共 260 字,大约阅读时间需要 1 分钟。

【题意】给定无向图,现在可能有一些点已经被删除,只给出信息是c个点未被删除且不能到达结点1,求最少的删除点个数。

【算法】最小割

【题解】本题和1的区别是:1求的是最少的不能到达1的结点数,那么就把损坏点圈缩在不可达点的邻点。

本体求的是删除最少的点使c个点不可达,这样的要求就是典型的最小割。

每个点x连向x',容量为1,若是未被删除点则容量为inf。

将1的设为S,将报告点的出点连向T,问题转化为S-T最小割。

 

转载于:https://www.cnblogs.com/onioncyc/p/7603325.html

你可能感兴趣的文章
Comet:基于 HTTP 长连接的“服务器推”技术
查看>>
BZOJ 2733: [HNOI2012]永无乡 启发式合并treap
查看>>
四种方法校验数组中是否包含某个指定的字符串
查看>>
29、Java并发性和多线程-非阻塞算法
查看>>
安装OpenResty开发环境
查看>>
第0课 从0开始
查看>>
hadoop无法启动DataNode问题
查看>>
java泛型中<?>和<T>区别
查看>>
这里是指推送通知跟NSNotification有区别:
查看>>
用户ID的代码生成
查看>>
win7经常出现“关闭xxxx前您必须关闭所有会话框”
查看>>
SNMP安全配置的两种方法(也可同一时候兼顾配置两种方法)
查看>>
MongoDB 自己定义函数
查看>>
Summary Day30
查看>>
逆向输出回环数组
查看>>
自己动手,实现“你的名字”滤镜
查看>>
高清摄像头MIPI CSI2接口浅解【转】
查看>>
C# CancellationTokenSource和CancellationToken的实现
查看>>
PCIE BAR空间
查看>>
winform命名规范
查看>>