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

相关文章

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Spring Boot结成MyBatis-Plus最全配置指南

《SpringBoot结成MyBatis-Plus最全配置指南》本文主要介绍了SpringBoot结成MyBatis-Plus最全配置指南,包括依赖引入、配置数据源、Mapper扫描、基本CRUD操... 目录前言详细操作一.创建项目并引入相关依赖二.配置数据源信息三.编写相关代码查zsRArly询数据库数

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

SpringBoot使用OkHttp完成高效网络请求详解

《SpringBoot使用OkHttp完成高效网络请求详解》OkHttp是一个高效的HTTP客户端,支持同步和异步请求,且具备自动处理cookie、缓存和连接池等高级功能,下面我们来看看SpringB... 目录一、OkHttp 简介二、在 Spring Boot 中集成 OkHttp三、封装 OkHttp

JavaScript错误处理避坑指南

《JavaScript错误处理避坑指南》JavaScript错误处理是编程过程中不可避免的部分,它涉及到识别、捕获和响应代码运行时可能出现的问题,本文将详细给大家介绍一下JavaScript错误处理的... 目录一、错误类型:三大“杀手”与应对策略1. 语法错误(SyntaxError)2. 运行时错误(R

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Python使用date模块进行日期处理的终极指南

《Python使用date模块进行日期处理的终极指南》在处理与时间相关的数据时,Python的date模块是开发者最趁手的工具之一,本文将用通俗的语言,结合真实案例,带您掌握date模块的六大核心功能... 目录引言一、date模块的核心功能1.1 日期表示1.2 日期计算1.3 日期比较二、六大常用方法详

Linux系统之主机网络配置方式

《Linux系统之主机网络配置方式》:本文主要介绍Linux系统之主机网络配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、查看主机的网络参数1、查看主机名2、查看IP地址3、查看网关4、查看DNS二、配置网卡1、修改网卡配置文件2、nmcli工具【通用

MySQL中慢SQL优化方法的完整指南

《MySQL中慢SQL优化方法的完整指南》当数据库响应时间超过500ms时,系统将面临三大灾难链式反应,所以本文将为大家介绍一下MySQL中慢SQL优化的常用方法,有需要的小伙伴可以了解下... 目录一、慢SQL的致命影响二、精准定位问题SQL1. 启用慢查询日志2. 诊断黄金三件套三、六大核心优化方案方案