新泰网站制作,网站首页内容,在线制作电子公章免费公章在线生成,中科诚建建设工程有限公司网站381. 有线电视网络 - AcWing题库
给定一张 n 个点 m 条边的无向图#xff0c;求最少去掉多少个点#xff0c;可以使图不连通。
如果不管去掉多少个点#xff0c;都无法使原图不连通#xff0c;则直接返回 n。
输入格式
输入包含多组测试数据。
每组数据占一行#xf…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则得到的简单割的割边和就是选到的点的数量则可以得到割点集的点的数量 简单割的割的容量和 因此最小割点集 最小割
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemap
#includesstream
#includedeque
#includeunordered_map
#includeunordered_set
#includebitset
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pairint, int PII;
const int N 1e2 10, M (250050) * 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;
}
