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

相关文章

SpringBoot请求参数接收控制指南分享

《SpringBoot请求参数接收控制指南分享》:本文主要介绍SpringBoot请求参数接收控制指南,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring Boot 请求参数接收控制指南1. 概述2. 有注解时参数接收方式对比3. 无注解时接收参数默认位置

CentOS7更改默认SSH端口与配置指南

《CentOS7更改默认SSH端口与配置指南》SSH是Linux服务器远程管理的核心工具,其默认监听端口为22,由于端口22众所周知,这也使得服务器容易受到自动化扫描和暴力破解攻击,本文将系统性地介绍... 目录引言为什么要更改 SSH 默认端口?步骤详解:如何更改 Centos 7 的 SSH 默认端口1

SpringBoot多数据源配置完整指南

《SpringBoot多数据源配置完整指南》在复杂的企业应用中,经常需要连接多个数据库,SpringBoot提供了灵活的多数据源配置方式,以下是详细的实现方案,需要的朋友可以参考下... 目录一、基础多数据源配置1. 添加依赖2. 配置多个数据源3. 配置数据源Bean二、JPA多数据源配置1. 配置主数据

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件(txt,xls,csv,sql,二进制文件)的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1

SpringBoot中配置Redis连接池的完整指南

《SpringBoot中配置Redis连接池的完整指南》这篇文章主要为大家详细介绍了SpringBoot中配置Redis连接池的完整指南,文中的示例代码讲解详细,具有一定的借鉴价值,感兴趣的小伙伴可以... 目录一、添加依赖二、配置 Redis 连接池三、测试 Redis 操作四、完整示例代码(一)pom.

Linux内核参数配置与验证详细指南

《Linux内核参数配置与验证详细指南》在Linux系统运维和性能优化中,内核参数(sysctl)的配置至关重要,本文主要来聊聊如何配置与验证这些Linux内核参数,希望对大家有一定的帮助... 目录1. 引言2. 内核参数的作用3. 如何设置内核参数3.1 临时设置(重启失效)3.2 永久设置(重启仍生效

Python列表去重的4种核心方法与实战指南详解

《Python列表去重的4种核心方法与实战指南详解》在Python开发中,处理列表数据时经常需要去除重复元素,本文将详细介绍4种最实用的列表去重方法,有需要的小伙伴可以根据自己的需要进行选择... 目录方法1:集合(set)去重法(最快速)方法2:顺序遍历法(保持顺序)方法3:副本删除法(原地修改)方法4:

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

PyInstaller打包selenium-wire过程中常见问题和解决指南

《PyInstaller打包selenium-wire过程中常见问题和解决指南》常用的打包工具PyInstaller能将Python项目打包成单个可执行文件,但也会因为兼容性问题和路径管理而出现各种运... 目录前言1. 背景2. 可能遇到的问题概述3. PyInstaller 打包步骤及参数配置4. 依赖

Nginx中配置HTTP/2协议的详细指南

《Nginx中配置HTTP/2协议的详细指南》HTTP/2是HTTP协议的下一代版本,旨在提高性能、减少延迟并优化现代网络环境中的通信效率,本文将为大家介绍Nginx配置HTTP/2协议想详细步骤,需... 目录一、HTTP/2 协议概述1.HTTP/22. HTTP/2 的核心特性3. HTTP/2 的优