381. 有线电视网络(网络流,最小割,《算法竞赛进阶指南》)

2024-03-03 08:28

本文主要是介绍381. 有线电视网络(网络流,最小割,《算法竞赛进阶指南》),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

381. 有线电视网络 - AcWing题库

给定一张 n 个点 m 条边的无向图,求最少去掉多少个点,可以使图不连通。

如果不管去掉多少个点,都无法使原图不连通,则直接返回 n。

输入格式

输入包含多组测试数据。

每组数据占一行,首先包含两个整数 n 和 m,接下来包含 m 对形如 (x,y) 的数对,形容点 x 与点 y 之间有一条边。

数对 (x,y) 中间不会包含空格,其余地方用一个空格隔开。

输出格式

每组数据输出一个结果,每个结果占一行。

数据范围

0≤n≤50

输入样例:
0 0
1 0
3 3 (0,1) (0,2) (1,2)
2 0
5 7 (0,1) (0,2) (1,3) (1,2) (1,4) (2,3) (3,4)
输出样例:
0
1
3
0
2

解析: 

通过删除某些点让无向图不连通。

如果是删除某些边使得无向图不连通,我们很容易想到使用最小割算法将割边删去。通过枚举源点 S 和汇点 T,然后使用最小割算法处理。

但本题要求将点删除,而非将边删除。我们需要将点转换成边看看是否能使用最小割算法。

拆点:

使用常见的拆点方式,将点拆成出点和入点,且出点和入点之间连一条边,边权为1,对应本题中要求求得点得数量。

简单割处理:  

由于本题只能删除点而不能删除边,所以我们要使得最小割算法不删除原图得边:将原图的边的容量设为正无穷。(最小割算法中的常用技巧,将不希望作为割边的边的容量设为正无穷) 

定义简单割:割边仅为有限容量的边形成的割称为简单割

 简单割具体证明参考:2325. 有向图破坏(二分图,最小点权覆盖,最小割,网络流)-CSDN博客 

证明简单割与要删掉的点的点割集存在一一对应的关系:

简单割=> 点割集
因为我们通过简单割求出的割边都是点内部的边,当我们把简单割里的边全删掉后,源点和汇点则不会联通了,这些构成“内部边”的点的集合就是点割集。

下面用反证法证明上面构造出来的点割集一定是符合题意的要删掉的点:

假设上面构造出来的点割集不符合题意,即把上面所有的点删掉,在原图里依然存在从源点到达汇点的路径,说明在原图中,存在一条不经过我们构造出来的点割集里的点的路径即不经过“点内部的边”,依然能从源点到达汇点,对应到流网络里则是存在一条从源点到汇点的不经过割边的路径,则说明源点与汇点在一个集合里,说明这不是一个割,与前提矛盾。因此反证得证。

点割集=> 简单割
这里的点割集指的是“极小点割集”

构造简单割的方法:

从源点开始dfs一遍,若经过点割集里的点,则停下不往前搜,若不是则往前搜,每次把搜到的点打个标记,这样标记了的点就是S集合,没有标记的点就是T集合,构成一个简单割C[S,T]因此我们可以证出简单割与割点集存在一一对应的关系。

考虑数量关系
由于我们建边的时候把入点到出点的边的容量设为1,则得到的简单割的割边和就是选到的点的数量,则可以得到:割点集的点的数量 = 简单割的割的容量和 ,因此:最小割点集 = 最小割

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1e2 + 10, M = (2500+50) * 2 + 10, INF = 0x3f3f3f3f;
int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];void add(int a, int b, int c) {e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}bool bfs() {int hh = 0, tt = 0;memset(d, -1, sizeof d);q[0] = S, d[S] = 0, cur[S] = h[S];while (hh <= tt) {int t = q[hh++];for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i];if (d[j] == -1 && f[i]) {d[j] = d[t] + 1;cur[j] = h[j];if (j == T)return 1;q[++tt] = j;}}}return 0;
}int find(int u, int limit) {if (u == T)return limit;int flow = 0;for (int i = cur[u]; i != -1 && flow < limit; i = ne[i]) {int j = e[i];cur[u] = i;if (d[j] == d[u] + 1 && f[i]) {int t = find(j, min(f[i], limit - flow));if (!t)d[j] = -1;f[i] -= t, f[i ^ 1] += t, flow += t;}}return flow;
}int dinic() {int ret = 0, flow;while (bfs())while (flow = find(S, INF))ret += flow;return ret;
}int main() {while (cin >> n >> m) {memset(h, -1, sizeof h);idx = 0;for (int i = 0; i < n; i++) {add(i, i + n, 1);}for (int i = 1,a,b; i <= m; i++) {scanf(" (%d,%d)", &a, &b);add(n + a, b, INF);add(n + b, a, INF);}int ans = n;for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++) {S = n + i, T = j;for (int k = 0; k < idx; k += 2) {f[k] += f[k ^ 1];f[k ^ 1] = 0;}ans = min(ans, dinic());}}cout << ans << endl;}return 0;
}

这篇关于381. 有线电视网络(网络流,最小割,《算法竞赛进阶指南》)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/769051

相关文章

MySQL进阶之路索引失效的11种情况详析

《MySQL进阶之路索引失效的11种情况详析》:本文主要介绍MySQL查询优化中的11种常见情况,包括索引的使用和优化策略,通过这些策略,开发者可以显著提升查询性能,需要的朋友可以参考下... 目录前言图示1. 使用不等式操作符(!=, <, >)2. 使用 OR 连接多个条件3. 对索引字段进行计算操作4

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

Nginx实现动态封禁IP的步骤指南

《Nginx实现动态封禁IP的步骤指南》在日常的生产环境中,网站可能会遭遇恶意请求、DDoS攻击或其他有害的访问行为,为了应对这些情况,动态封禁IP是一项十分重要的安全策略,本篇博客将介绍如何通过NG... 目录1、简述2、实现方式3、使用 fail2ban 动态封禁3.1 安装 fail2ban3.2 配

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Java中String字符串使用避坑指南

《Java中String字符串使用避坑指南》Java中的String字符串是我们日常编程中用得最多的类之一,看似简单的String使用,却隐藏着不少“坑”,如果不注意,可能会导致性能问题、意外的错误容... 目录8个避坑点如下:1. 字符串的不可变性:每次修改都创建新对象2. 使用 == 比较字符串,陷阱满

JavaScript中的reduce方法执行过程、使用场景及进阶用法

《JavaScript中的reduce方法执行过程、使用场景及进阶用法》:本文主要介绍JavaScript中的reduce方法执行过程、使用场景及进阶用法的相关资料,reduce是JavaScri... 目录1. 什么是reduce2. reduce语法2.1 语法2.2 参数说明3. reduce执行过程

python使用fastapi实现多语言国际化的操作指南

《python使用fastapi实现多语言国际化的操作指南》本文介绍了使用Python和FastAPI实现多语言国际化的操作指南,包括多语言架构技术栈、翻译管理、前端本地化、语言切换机制以及常见陷阱和... 目录多语言国际化实现指南项目多语言架构技术栈目录结构翻译工作流1. 翻译数据存储2. 翻译生成脚本

使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

《使用sql-research-assistant进行SQL数据库研究的实战指南(代码实现演示)》本文介绍了sql-research-assistant工具,该工具基于LangChain框架,集... 目录技术背景介绍核心原理解析代码实现演示安装和配置项目集成LangSmith 配置(可选)启动服务应用场景

如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别详解

《如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别详解》:本文主要介绍如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别的相关资料,描述了如何使用海康威视设备网络SD... 目录前言开发流程问题和解决方案dll库加载不到的问题老旧版本sdk不兼容的问题关键实现流程总结前言作为

SQL Server数据库迁移到MySQL的完整指南

《SQLServer数据库迁移到MySQL的完整指南》在企业应用开发中,数据库迁移是一个常见的需求,随着业务的发展,企业可能会从SQLServer转向MySQL,原因可能是成本、性能、跨平台兼容性等... 目录一、迁移前的准备工作1.1 确定迁移范围1.2 评估兼容性1.3 备份数据二、迁移工具的选择2.1