最小割-poj-2914

简介: poj-2914-Minimum Cut Description Given an undirected graph, in which two vertices can be connected by multiple edges, what is the size of the minimum cut of the graph? i.e. how many edges must b

poj-2914-Minimum Cut

Description

Given an undirected graph, in which two vertices can be connected by multiple edges, what is the size of the minimum cut of the graph? i.e. how many edges must be removed at least to disconnect the graph into two subgraphs?

Input

Input contains multiple test cases. Each test case starts with two integers N and  M (2 ≤ ≤ 500, 0 ≤ ≤ × (N − 1) ⁄ 2) in one line, where N is the number of vertices. Following are M lines,  each line contains M integers A, B and C (0 ≤ A, B < N, A ≠ B, C > 0), meaning that there C edges connecting vertices A and B.

Output

There is only one line for each test case, which contains the size of the minimum cut of the graph.  If the graph is disconnected, print 0.

Sample Input

3 3

0 1 1

1 2 1

2 0 1

4 3

0 1 1

1 2 1

2 3 1

8 14

0 1 1

0 2 1

0 3 1

1 2 1

1 3 1

2 3 1

4 5 1

4 6 1

4 7 1

5 6 1

5 7 1

6 7 1

4 0 1

7 3 1

Sample Output

2

1

2

微笑题目大意:有重边的无向图,至少删去多少条边能使其变为非连通图?

分析:传统最小割最大流算法需要枚举汇点,复杂度为O(n^4)以上,故有时会超时。本题用Stoer-Wagner 算法。

微笑Stoer-Wagner 算法用来求无向图 G=(V, E)的最小割。

算法基于这样一个原理:定义图G的最小割为MinCut,对于任意顶点s,t VMinCut=min(s-t最小割,将sv缩点之后的MinCut)。在此不予证明。

Stoer-Wagner 算法流程:

1. 初始置最小割MinCut INT_MAX

2. 在 G中求出任意 s-t 最小割 c,更新MinCut = min(MinCut, c) 

3. 对 G中的顶点s,t做缩点操作。若G中顶点已被缩为一个,当前MinCut即为所求。 

----缩点操作:

ab进行缩点: 删掉点 a, b 及边(a, b),加入新节点 c,对于任意 vmat(c,v) = mat(v,c) = mat(a, v) + mat(b,v)  

---求 G=(V, E)中任意 s-t 最小割的算法:

为点集,x不属于A,定义dist[x] = mat(v[i], x)v[i]

1. 初始令集合 A={a}a为 V中任意点 。

2. 选取 V - A中的 dis[ x ]最大的点 x加入集合 

3.更新V-A中顶点的dist[ ]

4.|A|=|V|,结束。令倒数第二个加入 A的点为 s,最后一个加入 A的点为 t,则s-t 最小割为dist[t]

微笑


 

目录
相关文章
|
Java 数据库连接 数据安全/隐私保护
利用开源工具实现轻量级上网行为审计(来源ispublic.com)
来源ispublic.com Google上貌似找不到利用开源软件实现上网行为审计的文章——这也难怪,开源在国内并不流行,而上网行为审计在国外也不流行。
1715 0
|
8月前
|
移动开发 前端开发 JavaScript
HTML5实现好看的端午节网页源码
HTML5实现好看的端午节网页源码,包含十个页面:网站首页、端午节介绍、由来、习俗、文化、美食、故事、民谣、联系我们及登录/注册。页面设计简洁美观,内容丰富,兼容手机端,代码规范且注释完整,易于扩展和修改。提供完整的源码下载和视频演示,方便学习和使用。
239 3
|
3月前
|
存储 人工智能 自然语言处理
Lakehouse x AI ,打造智能 BI 新体验
本文整理自瓴羊的王璟尧老师与镜舟科技石强老师的联合分享,围绕 Quick BI 在智能 BI 场景中的落地实践,深入探讨了 StarRocks 如何凭借 MPP 架构、实时分析能力与 AI 原生支持,成为智能分析的理想 Lakehouse 引擎底座,助力 BI 从“被动查询”迈向“主动决策”,开启数据“会说话”的新体验。
|
机器学习/深度学习 人工智能 监控
基于YOLOv8的人体检测、行人识别项目|完整源码数据集+PyQt5界面+完整训练流程+开箱即用!
本项目基于YOLOv8实现人体检测与行人识别,集成PyQt5图形界面,支持图片、视频、摄像头等多种输入方式。包含完整训练代码、数据集及部署教程,开箱即用,适用于安防监控、人数统计等场景。
|
4月前
|
缓存 Windows
电脑小白必看:C 盘满了怎么清理?软件搬到 D 盘的超简单步骤
C盘空间不足导致电脑卡顿?试试这些方法优化!首推FreeMove工具,不到1MB,简单两步搬软件,解放C盘空间。此外,清理临时文件、转移用户文件夹至D盘、调整虚拟内存位置、使用符号链接等技巧也能有效缓解压力。注意:系统核心目录不可移动,操作前请备份重要数据,确保安全!
310 5
|
Prometheus 监控 关系型数据库
数据库实时监控功能
【6月更文挑战第9天】数据库实时监控功能
369 4
|
关系型数据库 MySQL
MySQL 的 union 和union all 的区别
【5月更文挑战第4天】MySQL 的 union 和union all 的区别
525 7
Linux磁盘配额
在Linux系统中,当用户的空间占用接近或超过预设的软限制时,系统会警告用户磁盘空间将满。软限制是允许用户使用的磁盘空间的最大值,在此限制下,用户仍有宽限期来减少空间使用。如果在宽限期内用户未减少空间占用,达到硬限制,软限制将升级为硬限制。硬限制是用户可以使用的绝对最大值。默认的宽限期是7天,如果超过这个期限,用户的空间限制会立即降低到硬限制。
|
存储 弹性计算 安全
阿里云服务器租用价格参考,2核4G、4核8G、8核16G最新收费标准
阿里云服务器2核4G、4核8G、8核16G配置租用价格参考,2024年阿里云产品再一次降价,降价之后2核4G配置按量收费最低收费标准为0.225元/小时,按月租用标准收费标准为68.0元/1个月。4核8G配置的阿里云服务器按量收费标准最低为0.45元/小时,按月租用标准收费标准为216.0元/1个月。8核16G配置的阿里云服务器按量收费标准最低为0.9元/小时,按月租用标准收费标准为432.0元/1个月。云服务器实例规格的地域和实例规格不同,收费标准不一样,下面是2024年阿里云服务器2核4G、4核8G、8核16G配置的最新租用收费标准。
阿里云服务器租用价格参考,2核4G、4核8G、8核16G最新收费标准
|
人工智能 IDE JavaScript
分享一个很好用的代码辅助AI工具CodeGeeX2
分享一个很好用的代码辅助AI工具CodeGeeX2
358 1