最小割问题合集,最大权闭合图,最大密度子图,最小权点覆盖,最大权独立子图,OJ练习,代码详解

文章目录

  • 零、回顾
    • 1、流网络的割
    • 2、最小割问题
  • 一、最小割的应用
    • 1.1POJ1966 -- Cable TV Network
      • 1.1.1原题链接
      • 1.1.2思路分析
      • 1.1.3AC代码
    • 1.2ZOJ 2676 Network Wars
      • 1.2.1原题链接
      • 1.2.2思路分析
      • 1.2.3AC代码
    • 1.3OPTM - Optimal Marks
      • 1.3.1原题链接
      • 1.3.2思路分析
      • 1.3.3AC代码
  • 二、最大权闭合子图
    • 2.1什么是闭合子图?
    • 2.2最大权闭合子图
    • 2.3简单割
    • 2.4最小割与简单割与闭合子图之间的关系
      • 2.4.1最小割一定都是简单割
      • 2.4.2每一个闭合子图可以构造一个简单割
      • 2.4.3每一个简单割可以构造一个闭合子图
    • 2.5利用最小割求解最大权闭合子图
    • 2.6 练习之最大获利
      • 2.6.1原题链接
      • 2.6.2思路分析
      • 2.6.3AC代码
  • 三、最大密度子图
    • 3.1什么是图的密度?
    • 3.2求解思路
      • 3.2.1直接转化为最大权闭合图问题
      • 3.2.2 01最小割求解
    • 3.3更一般化的情况
      • 3.3.1只有边权
      • 3.3.2同时有边权点权
    • 3.4练习之Hard Life
      • 3.3.1原题链接
      • 3.3.2思路分析
      • 3.3.3AC代码
    • 3.5再看最大获利
      • 3.6.1原题链接
      • 3.6.2转化为最大密度子图问题
      • 3.6.2AC代码
  • 四、最小权点覆盖集
    • 4.1什么是点覆盖集
    • 4.2二分图的最小权点覆盖集与最小割的关系
      • 流网络的割一定是简单割
      • 简单割可以构造一个点覆盖集
      • 一个极小点覆盖集可以构造一个简单割
      • 最小割的容量和就是最小权点覆盖集的权值
    • 4.3 POJ2125Destroying The Graph
      • 4.3.1原题链接
      • 4.3.2思路分析
      • 4.3.3AC代码
  • 五、最大权独立集
    • 5.1什么是独立集
    • 5.2最大权独立集和最小权点覆盖集的互补关系
    • 5.3 P4474 王者之剑
      • 5.3.1原题链接
      • 5.3.2思路分析
      • 5.3.3AC代码
  • 六、OJ练习
    • 6.1P2762 太空飞行计划问题
      • 6.1.1原题链接
      • 6.1.2思路分析
      • 6.1.3AC代码
    • 6.2P3355 骑士共存问题
      • 6.2.1原题链接
      • 6.2.2思路分析
      • 6.2.3AC代码
  • 七、总结


零、回顾

1、流网络的割

流网络G = (V , E)的割(S , T)将V划分为S和T两部分,使得s∈S,t属于T,通过割的流量为S和T之间边上流量的代数和,但是割的容量仅包含从S到T的边的容量的代数和

如下图,割(S,T)的流量f(S,T) = 12 - 4 + 11 = 19

容量c(S,T) = 12 + 14 = 26在这里插入图片描述

我们称容量最小的割为最小割

可以证明f(S , T) = | f | ≤ c(S, T)

由最大流最小割定理,若f是G的一个最大流,那么存在最小割(S , T),有**| f | = c(S , T)**

2、最小割问题

最小割从定义上讲,无非就是讲流网络分成分别包含源点汇点的S,T两部分,连接两个集合的边割去后流网络断流。

而实际应用中,经常是对问题建模,然后将原问题的解和最小割对应,然后通过最大流算法求解最小割来求解原问题的解。

常见问题有:最大权闭合子图,最大密度子图,最小权覆盖集,最大权独立集、以及比较考验思维将问题与割相联系的问题。总之最小割问题相较于网络流问题来说,更加抽象,需要一定量的练习来熟悉这种建模思维。


一、最小割的应用

1.1POJ1966 – Cable TV Network

1.1.1原题链接

1966 – Cable TV Network (poj.org)

1.1.2思路分析

我们要找到使得原图不连通的最小删除点数。这个还是可以往最小割上靠的,因为我们的割删除一些边使得两个集合不连通。

但是这道题删除的是点,而我们割删的是边,我们怎么做呢?——拆点。

我们将原图每个点u拆为u和u + n,分别代表入点和出点,入点向出点连边

一定有一个答案是删除后出现两个集合S,T,那么我们可以将其看作一个割,割掉的点对应割掉的边即入点和出点的边

然后为了让答案和最小割联系起来,对于非源点汇点的点,我们从入点向出点连容量为1的边,然后为了保证最小割割掉的是点即入点和出点连的边,所以对于原图的其它边我们赋容量为正无穷,这样最小割一定不会包含这些边

然后对于源点和汇点自然是不能割的,所以其入点到出点的边的容量为正无穷

这样我们建立了一个流网络,流网络的最小割对应原题的解:最小割的边一定只包含入点和出点的边,因为最小割有限,不可能包含那些正无穷的边,那么最小割就对应了一组割点集,最小割是使得流网络断流的最小割,而这些割边的容量是1,所以就对应了割掉的点的数目,所以最小割就是原题的解。

1.1.3AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define sc scanf
#define mkp make_pair
typedef pair<int, int> PII;
const int N = 105, M = (50 * 50 + N) << 1, inf = 1e9;
struct edge{int v, c, nxt;
}edges[M];
int n, m, s, t;
int head[N], cur[N], q[N], d[N], b, f, idx;
PII es[N*N];
void addedge(int u, int v, int c){edges[idx].v = v, edges[idx].c = c, edges[idx].nxt = head[u], head[u] = idx++;
}
void add(int u, int v, int c){addedge(u, v, c), addedge(v, u, 0);
}
bool bfs(){b = f = 0, memset(d, 0, sizeof d), d[q[b++] = s] = 1;while(b - f){int u = q[f++];for(int i = head[u]; ~i; i = edges[i].nxt){int v = edges[i].v;if(!d[v] && edges[i].c){d[q[b++] = v] = d[u] + 1;if(v == t) return true;}}}return false;
}
int dfs(int u, int lim){if(u == t) return lim;int res = 0;for(int i = cur[u]; ~i && lim; i = edges[i].nxt){int v = edges[i].v;if(d[v] == d[u] + 1 && edges[i].c){int incf = dfs(v, min(lim, edges[i].c));if(!incf) d[v] = 0;res += incf, lim -= incf, edges[i].c -= incf, edges[i^1].c += incf;}}return res;
}
void build(){memset(head, -1, sizeof head), idx = 0;for(int i = 0; i < n; i++)if(i == s || i == t) add(i, i + n, inf);elseadd(i, i + n, 1);for(int i = 0, a, b; i < m; i++){a = es[i].first, b = es[i].second;add(a + n, b, inf), add(b + n, a, inf);}
}
int dinic(){build();int res = 0;while(bfs())memcpy(cur, head, sizeof head), res += dfs(s, inf);return res;
}
int main(){//freopen("in.txt", "r", stdin);while(~sc("%d%d", &n, &m)){for(int i = 0, a, b; i < m; i++){sc(" (%d,%d)", &a, &b);es[i] = mkp(a, b);}		if(n == 1){puts("1");continue;}if(!m){puts("0");continue;}if(m == (n - 1) * n / 2){printf("%d\n", n);continue;}int res = n;for(s = 0; s < n; s++)for(t = s + 1; t < n; t++)res = min(res, dinic());printf("%d\n", res);}return 0;
}

1.2ZOJ 2676 Network Wars

1.2.1原题链接

2676 Network Wars - ZOJ Problem Set (pintia.cn)

1.2.2思路分析

题目人话就是求一个使得原图不连通的割集,然后割边的权值和为c,边数为k,求一个割集使得c / k最小

但看使得c / k最小,这是一个很明显的01分数规划问题,0 - 1分数规划问题都可以二分来求答案。

我们考虑符合题意得最小c / k = mid,那么

<=> c = k * mid,而c是k条边累加得来的 <=> Σ c - mid = 0

如果 Σ c - mid 最小值小于0,说明我们答案枚举大了,缩小二分上界,否则缩小二分下界

那么怎么求 Σ c - mid 最小值呢?

如果直接想当然的认为原图每条边容量减去mid,然后最小割就是 Σ c - mid 的话那么是不对的。

因为题目只要求一个割集使得原图不连通使得c / k最小,这说明割集是有可能包含最小割中S,T中的边的

所以我们该如何入手去将 c / k 最小值与最小割联系呢?

我们考虑将原图每条边容量减去mid,那么我们对于容量为负的边,显然可以使得c / k变小,换言之可以使得Σ c - mid变小,所以负数边显然要选上,那么对于正数边,每选一条c / k都会变大,所以要尽可能少选,所以我们发现当我们把负数边剔除后, Σ c - mid 最小就变成了从剩下的边中挑出一些边使得原图不连通且容量和最小,因为剩下的c都大于mid,多选一条结果都会变大,所以要尽可能少选,我们发现这一部分的和就是剔除负数边后的最小割

所以对于二分答案mid, Σ c - mid的最小值就是:
原图每条边容量减去mid,负数边直接加到答案里面,然后正反边容量置为0

然后求最小割累加到答案里面,就是Σ c - mid的最小值

然后check函数就写出来了,二分出答案后,我们还要求出割掉的边:包含原图中权值的小于答案的边,以及S,T之间的割边

对于S,T的割边直接dfs,我们沿着容量不为0的边从s出发去遍历,那些只有一个端点被访问的边就是最小割里的边,然后权值小于答案的边我们读数据的时候就存下了所有边的权值,直接找就行

1.2.3AC代码

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define sc scanf
const int N = 105, M = 810, inf = 1e9;
int head[N], cur[N], q[N], d[N], b, f, s, t, n, m, idx;
double w[M];
bool vis[N];
double eps = 1e-8;
struct edge{int v, nxt;double c;
}edges[M]; 
void addedge(int u, int v, double c){w[idx] = c, edges[idx] = {v, head[u], c}, head[u] = idx++;
}
void add(int u, int v, double c){addedge(u, v, c), addedge(v, u, c);
}
bool bfs(){memset(d, 0, sizeof d), b = f = 0, d[q[b++] = s] = 1;while(b - f){int u = q[f++];for(int i = head[u]; ~i; i = edges[i].nxt){int v = edges[i].v;if(!d[v] && edges[i].c){d[q[b++] = v] = d[u] + 1;if(v == t) return true;}}}return false;
}
double dfs(int u, double lim){if(u == t) return lim;double res = 0;for(int i = cur[u]; ~i && lim; i = edges[i].nxt){cur[u] = i;int v = edges[i].v;if(d[v] == d[u] + 1 && edges[i].c){double incf = dfs(v, min(lim, edges[i].c));if(!incf) d[v] = 0;res += incf, lim -= incf, edges[i].c -= incf, edges[i^1].c += incf;}}return res;
}
double dinic(){double res = 0;while(bfs())memcpy(cur, head, sizeof head), res += dfs(s, inf);return res;
}
bool check(double mid){double ret = 0;for(int i = 0; i < idx; i += 2) {if(w[i] <= mid) ret += w[i] - mid, edges[i].c = edges[i^1].c = 0;else edges[i].c = edges[i^1].c = w[i] - mid;}return ret + dinic() < 0;
}
void getcut(int u){vis[u] = 1;for (int i = head[u]; ~i; i = edges[i].nxt) {int v = edges[i].v;if (!vis[v] && edges[i].c > eps)getcut(v);}
}
int main(){//freopen("in.txt", "r", stdin);while(~sc("%d%d",&n, &m)){if(s) puts("");s = 1, t = n, memset(head, -1, sizeof head), idx = 0;double c;for(int i = 0, a, b; i < m; i++) sc("%d%d%lf", &a, &b, &c), add(a, b, c);double l = 0, ans = 1e7, r = 1e7;int tot = 0;while(r - l >= eps){double mid = (l + r) / 2;check(mid) ? ans = r = mid : l = mid;}memset(vis, 0, sizeof vis);vector<int> id;getcut(s);for(int i = 0; i < idx; i += 2) if(vis[edges[i].v] + vis[edges[i^1].v] == 1 || w[i] <= ans) tot++, id.emplace_back(i / 2 + 1);printf("%d\n", tot);for(auto x : id) printf("%d ", x);}return 0;
}

1.3OPTM - Optimal Marks

1.3.1原题链接

SPOJ.com - Problem OPTM

1.3.2思路分析

每个节点都有标号,对于一个边而言,其贡献就是两个节点的标号异或和,一些节点有初始标号,让我们为剩下的点赋标号使得所有边的贡献和最小。

每个边的贡献我们可以按位来看,贡献和就是每个边对每个位的贡献和。这样也就31个位,算31次,算是一个小常数,也是我们处理这类问题的通用方式。

那么怎么按位求贡献呢?

对于第i位而言,原图中的点可以分为两部分S,T,S内点第i位都是1,T中都是0

那么我们的贡献就是S、T之间的边,因为原图任意一种划分方式都是一个割,而我们建立的一个割也都对应了原图的一种划分方式,而且原图的第i位的贡献对应我们S、T之间的边的容量(容量为1)和即最小割

那么就可以这样建模:对于原图中相连的点a,b,我们连a->b容量为1的边以及b->a容量为1的边,然后有些点是有标号的,第i位为1的直接从s向其连一条正无穷的边,为0的则从其向汇点连正无穷的边,然后最小割就是答案

1.3.3AC代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 505, M = (N * 2 + 3000) << 1, inf = 1e9;
struct edge{int v, c, nxt;
}edges[M];
int n, m, s, t, K;
int d[N], q[N], head[N], cur[N], w[N], p[N], idx, b, f;
PII es[3010];
bool vis[N];
void addedge(int u, int v, int c){edges[idx] = {v, c, head[u]}, head[u] = idx++;
}
void add(int u, int v, int c, int d){addedge(u, v, c), addedge(v, u, d);
}
bool bfs(){memset(d, 0, sizeof d), b = f = 0, d[q[b++] = s] = 1;while(b - f){int u = q[f++];for(int i = head[u]; ~i; i = edges[i].nxt){int v = edges[i].v;if(!d[v] && edges[i].c){d[q[b++] = v] = d[u] + 1;if(v == t) return true;}}}return false;
}
int dfs(int u, int lim){if(u == t) return lim;int res = 0;for(int i = cur[u]; ~i && lim; i = edges[i].nxt){int v = edges[i].v;cur[u] = i;if(d[v] == d[u] + 1 && edges[i].c){int incf = dfs(v, min(edges[i].c, lim));if(!incf) d[v] = 0;edges[i].c -= incf, edges[i^1].c += incf, lim -= incf, res += incf;}}return res;
}
int dinic(int k){memset(head, -1, sizeof head), idx = 0;for(int i = 0; i < m; i++)add(es[i].first, es[i].second, 1, 1);for(int i = 1; i <= n; i++)if(~w[i]) {if(w[i] >> k & 1)add(s, i, inf, 0);elseadd(i, t, inf, 0);}int res = 0;while(bfs()) memcpy(cur, head, sizeof head), res += dfs(s , inf);return res;
}
void getp(int u, int k){vis[u] = 1, p[u] |= (1 << k);for(int i = head[u]; ~i; i = edges[i].nxt){int v = edges[i].v;if(!vis[v] && edges[i].c)getp(v, k);}
}void solve(){cin >> n >> m, memset(w, -1, sizeof w), memset(p, 0, sizeof p), s = 0, t = n + 1;for(int i = 0, a, b; i < m; i++) cin >> es[i].first >> es[i].second;cin >> K;for(int i = 0, a; i < K; i++) cin >> a, cin >> w[a], p[a] = w[a];for(int i = 0; i <= 30; i++) memset(vis, 0, sizeof vis), dinic(i), getp(s, i);for(int i = 1; i <= n; i++) cout << p[i] << '\n';
}
int main(){//freopen("in.txt", "r", stdin);ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int _ = 1;cin >> _;while(_--)solve();return 0;
}

上面的问题都是最小割的比较明显的直接应用,而接下来的最大权闭合子图以及最大密度子图问题就略显抽象了。

二、最大权闭合子图

2.1什么是闭合子图?

给有向图G(V, E),如果子图G’(V’, E’)满足:原图中V’发出的所有边都指向G’内的点,那么G‘就是原图G的一个闭合子图

2.2最大权闭合子图

当原图的每个点都有了权值,那么最大权闭合子图就是所有闭合子图中权值和最大的那个

2.3简单割

为了解决最大权闭合子图问题,我们定义”简单割“这一概念,对于原图内边我们赋正无穷容量,然后对于点权为正值的点,从源点向其连容量为权值的有向边,权值为负值的点,向汇点连接容量为权值相反数的有向边。

对于割集只在s和V之间以及V和t之间的割,我们称之为简单割

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

2.4最小割与简单割与闭合子图之间的关系

2.4.1最小割一定都是简单割

证明:

最小割等于最大流,而从源点出发的流量都是有限值,所以所有可行流都是有限值,所以最小割是有限值,所以最小割割集不包含原图的边,所以最小割是简单割

2.4.2每一个闭合子图可以构造一个简单割

证明:

不妨设闭合子图点集为V’,将流网络分为:{s} + V‘、{t} + V - V’,那么流网络就分为了{s} + V‘和{t} + V - V’两部分,下面只需证明c<{s} + V‘、{t} + V - V’>是一个简单割

由于V‘是闭合子图的点集,所以V’发出所有边都指向V‘内的点,所以割集不包含从V‘到V - V’的边,所以割集只包含容量有限的边,所以是简单割

2.4.3每一个简单割可以构造一个闭合子图

证明:

对于简单割c<S, T>,从S - {s}中的任意一点发出的边的集合与原图边的交集的那些被边都指向S - {s}内,否则就存在某条原图的边在割集内,就不是简单割,矛盾。所以S - {s}就是一个闭合点集

所以我们证明出了所有最小割都是简单割,而且简单割和闭合子图之间的一一对应关系

2.5利用最小割求解最大权闭合子图

我们做如下规定:

对于最小割c<S, T>,有闭合点集V‘ = S - {s},记V’为V1,V - V‘为V2

从S到T的割的容量就是s到V2的边的容量 + V1到t的边的容量,因为s、t间无边,V1V2间的边不在简单割内(最小割是简单割)


c < S , T > = c < s , V 2 > + c < V 1 , t > = ∑ v ∈ V 1 , w v < 0 − w v + ∑ v ∈ V 2 , w v > 0 w v \begin{align} c<S, T> &= c<s, V2> + c<V1, t> \\ &= \sum_{v \in V1,w_{v} \lt 0}^{}-w_{v} + \sum_{v \in V2,w_{v} \gt 0}^{}w_{v} \end{align} c<S,T>=c<s,V2>+c<V1,t>=vV1,wv<0wv+vV2,wv>0wv
而对于闭合子图其点权和为:
w ( V 1 ) = ∑ v ∈ V 1 w v = ∑ v ∈ V 1 , w v > 0 w v + ∑ v ∈ V 1 , w v < 0 w v \begin{align} w(V1) &= \sum_{v \in V1} w_{v} \\ &= \sum_{v \in V1,w_{v} \gt 0}w_{v} + \sum_{v \in V1,w_{v} \lt 0}w_{v} \end{align} w(V1)=vV1wv=vV1,wv>0wv+vV1,wv<0wv
两式相加:
w ( V 1 ) + c < S , T > = ∑ v ∈ V 1 , w v > 0 w v + ∑ v ∈ V 2 , w v > 0 w v = ∑ v ∈ V , w v > 0 w v \begin{align} w(V1) + c<S, T> &= \sum_{v \in V1,w_{v} \gt 0}w_{v} + \sum_{v \in V2,w_{v} \gt 0}^{}w_{v} \\ &=\sum_{v \in V, w_{v} \gt 0} w_{v} \end{align} w(V1)+c<S,T>=vV1,wv>0wv+vV2,wv>0wv=vV,wv>0wv
右边就是原图中正点权之和,是一个定值

左边想要w(V1)最大,那么就要最小割最小,而最小割就是最小值,所以w(V1)就等于原图正点权和减去最小割!!!

2.6 练习之最大获利

2.6.1原题链接

[P4174 NOI2006] 最大获利 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

2.6.2思路分析

这个题目就很最大权闭合子图了,可以说是板子题。

如果要转这个用户的收益,就必须承担他要用的那些中转站的损失,这不就是选这个正权点就必须把他连接的负权点也选上,然后求一个最大点权和的方案,不就是一个最大权闭合子图问题吗。

经过前面的推导,我们发现求解方式是很简单的,对于中转站向汇点连边,用户则跟中转站连无穷边,源点向用户连边

然后用用户收益和减去最小割就是答案

后面我们学习最大密度子图后会重看这道题

2.6.3AC代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 55005, M = (50000 * 3 + 5000) << 1, inf = 1e9;
int n, m, sum;
int head[N], cur[N], d[N], q[N], b, f, s, t, idx;
struct edge{int v, c, nxt;
}edges[M];
void addedge(int u, int v, int c){edges[idx] = {v, c, head[u]}, head[u] = idx++;
}
void add(int u, int v, int c){addedge(u, v, c), addedge(v, u, 0);
}
bool bfs(){memset(d, 0, sizeof d), b = f = 0, d[q[b++] = s] = 1;while(b - f){int u = q[f++];for(int i = head[u]; ~i; i = edges[i].nxt){int v = edges[i].v;if(!d[v] && edges[i].c){d[q[b++] = v] = d[u] + 1;if(v == t) return true;}}}return false;
}
int dfs(int u, int lim){if(u == t) return lim;int res = 0;for(int i = cur[u]; ~i && lim; i = edges[i].nxt){int v = edges[i].v;cur[u] = i;if(d[v] == d[u] + 1 && edges[i].c){int incf = dfs(v, min(lim, edges[i].c));if(!incf) d[v] = 0;lim -= incf, res += incf, edges[i].c -= incf, edges[i ^ 1].c += incf;}}return res;
}
int dinic(){int res = 0;while(bfs())memcpy(cur, head, sizeof head), res += dfs(s, inf);return res;
}int main(){freopen("in.txt", "r", stdin);ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);memset(head, -1, sizeof head), idx = 0;cin >> n >> m, s = 0, t = n + m + 1;for(int i = 1, w; i <= n; i++) cin >> w, add(i, t, w);for(int i = 1, a, b, c; i <= m; i++){cin >> a >> b >> c;add(s, i + n, c), add(i + n, a, inf), add(i + n, b, inf), sum += c;}cout << sum - dinic();return 0;
} 

三、最大密度子图

更恶心的来了(

3.1什么是图的密度?

对于无向图G(V, E),其密度为边数与点数的比值

这显然是一个01分数规划问题,那么可以用二分来求解。

3.2求解思路

首先这是01规划问题,设最大值为g

那么|E| / |V| < g

|E| - g|V| < 0

求|E| - g|V|的最大值等价为求 g|V| - |E|的最小值

3.2.1直接转化为最大权闭合图问题

我们选择直接求|E| - g|V|的最大值,我们发现这个式子好像可以转化为最大权闭合图问题。

对于原图而言,选了一条边,那么这条边的两个顶点也要选,那么我们对原图的顶点赋点权-g,把原图的边看作一个点赋点权为1,然后向它的两个顶点连边,那么|E| - g|V|就是一个闭合图的点权,我们要求|E| - g|V|的最大值就等价为求新图的最大权闭合图

这还是比较好做的,建模后正权和减去最小割就行

3.2.2 01最小割求解

上面的做法由于开了新点,原来的一条边变成了两条边,是有额外开销的,我们考虑不转换的做法。

考虑:求|E| - g|V|的最大值就相当于求g|V| - |E|的最小值

然后注意到|E| = V内点的度 / 2 - 和V外点连的边数/2,前者记为du,后者记为c(u,v)
g ∣ V ∣ − ∣ E ∣ = ∑ u ∈ V g − ∑ v ∈ V ˉ ( d u 2 − c ( u , v ) 2 ) = ∑ u ∈ V ( g − d u 2 + ∑ v ∈ V ˉ c ( u , v ) 2 ) = 1 2 ∑ u ∈ V ( 2 g − d u + ∑ v ∈ V ˉ c ( u , v ) ) \begin{align} g|V| - |E| &= \sum_{u \in V}g - \sum_{v \in \bar{V}}(\frac{d_{u}}{2} - \frac{c(u, v)}{2}) \\ &=\sum_{u \in V}(g - \frac{d_{u}}{2} + \sum_{v \in \bar{V}} \frac{c(u, v)}{2}) \\ &= \frac{1}{2}\sum_{u \in V}(2g - d_{u} + \sum_{v \in \bar{V}} c(u, v)) \end{align} gVE=uVgvVˉ(2du2c(u,v))=uV(g2du+vVˉ2c(u,v))=21uV(2gdu+vVˉc(u,v))
化简到这里后,由于我们是为了和最小割联系起来,我们观察上式,2g - du是针对所有点的,我们可以考虑从所有点向汇点连接容量为 2g-du的边,但是为了防止容量小于0,所以实际上我们连接边的容量为 U + 2g-du

然后对于式子中的c(u, v)无非就是原图的边,所以我们将原图的边容量设置为1,然后由于所有点向汇点的边的容量都加上了U,所以我们从源点向所有点连接容量为U的边

对于任意最大密度子图是可以将原图划分为两个集合的:{s} + V, {t} + V’,而割集只包含s 到 V’、V到V‘、V到t的边,因为s、t间无边

然后我们尝试写出最小割的式子:
c ( S , T ) = C ( S , V ˉ ) + c ( V , t ) + c ( V , V ˉ ) = ∑ v ∈ V ˉ U + ∑ u ∈ V ( U + 2 g − d u + ∑ v ∈ V ˉ c ( u , v ) ) = n U + ∑ u ∈ V ( 2 g − d u + ∑ v ∈ V ˉ c ( u , v ) ) \begin{align} c(S, T) &= C(S, \bar{V}) + c(V, t) + c(V, \bar{V}) \\ &= \sum_{v \in \bar{V}}U + \sum_{u \in V}(U + 2g - d_{u} + \sum_{v \in \bar{V}} c(u, v))\\ &= nU + \sum_{u \in V}(2g - d_{u} + \sum_{v \in \bar{V}} c(u, v)) \end{align} c(S,T)=C(S,Vˉ)+c(V,t)+c(V,Vˉ)=vVˉU+uV(U+2gdu+vVˉc(u,v))=nU+uV(2gdu+vVˉc(u,v))
我们惊奇的发现我们要求最小值的那个式子出现在了最小割的右边,并且最小割等于一个常数加上它

那么g|V| - |E|取最小就等价于割取最小,那么最小值就是(最小割 - nU) / 2

3.3更一般化的情况

如果给定无向图增加了点权和边权后,让求最大密度子图,该如何求解?

3.3.1只有边权

这种情况最好处理,原先的度数变成每个点连接的边的权值和,然后原图边赋容量赋为边权即可。

此时答案仍为(最小割 - nU) / 2

3.3.2同时有边权点权

再次推导:

假设每个点有了点权pi

要求的密度为
∣ E ∣ + p ( V ) ∣ V ∣ \begin{align} \frac{|E| + p(V)}{|V|} \end{align} VE+p(V)
那么要最小化:
g ∣ V ∣ − p ( V ) − ∣ E ∣ = 1 2 ∑ u ∈ V ( 2 g − 2 p u − d u + ∑ v ∈ V ˉ c ( u , v ) ) \begin{align} g|V| - p(V) - |E| &= \frac{1}{2}\sum_{u \in V}(2g - 2p_{u} - d_{u} + \sum_{v \in \bar{V}} c(u, v)) \end{align} gVp(V)E=21uV(2g2pudu+vVˉc(u,v))
最小割为:
c ( S , T ) = n U + ∑ u ∈ V ( 2 g − 2 p u − d u + ∑ v ∈ V ˉ c ( u , v ) ) \begin{align} c(S, T) &= nU + \sum_{u \in V}(2g - 2p_{u} - d_{u} + \sum_{v \in \bar{V}} c(u, v)) \end{align} c(S,T)=nU+uV(2g2pudu+vVˉc(u,v))
我们发现结果仍为(最小割 - nU) / 2,只不过我们建模时,原图边的容量为原图边权,向汇点连边容量为U + 2g - du - pu

后面我们会再看最大获利这道题,发现最大权闭合图是可以转化为最大密度子图的

3.4练习之Hard Life

3.3.1原题链接

3155 – Hard Life (poj.org)

3.3.2思路分析

题目翻译成人话就是让找最大密度子图并输出

我们考虑U的取值,由于g为正值,U要比任意点度数大,那U直接取边数就行

然后按照上面的思路建图跑板子就行了

3.3.3AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 105, M = (N * 2 + 1000) << 1, inf = 1e9;
const double eps = 1e-8;
int n, m, s, t, ans;
int d[N], head[N], cur[N], q[N], dg[N], b, f, idx;
bool vis[N];
PII es[1005];
struct edge{int v, nxt;double c;
}edges[M];
void addedge(int u, int v, double c){edges[idx].c = c, edges[idx].v = v, edges[idx].nxt = head[u], head[u] = idx++;
}
void add(int u, int v, double c, double d){addedge(u, v, c), addedge(v, u, d);
}
bool bfs(){memset(d, 0, sizeof d), b = f = 0, d[q[b++] = s] = 1;while(b - f){int u = q[f++];for(int i = head[u]; ~i; i = edges[i].nxt){int v = edges[i].v;if(!d[v] && edges[i].c){d[q[b++] = v] = d[u] + 1;if(v == t) return true;}} } return false;
}
double dfs(int u, double lim){if(u == t) return lim;double res = 0;for(int i = cur[u]; ~i && lim; i = edges[i].nxt){int v = edges[i].v;if(d[v] == d[u] + 1 && edges[i].c){double incf = dfs(v, min(edges[i].c, lim));if(!incf) d[v] = 0;lim -= incf, res += incf, edges[i].c -= incf, edges[i ^ 1].c += incf;}}return res;
}
void build(double mid){memset(head, -1, sizeof head), idx = 0;for(int i = 0, a, b; i < m; i++) a = es[i].first, b = es[i].second, add(a, b, 1, 1);for(int i = 1; i <= n; i++)add(s, i, m, 0), add(i, t, m + mid * 2 - dg[i], 0);
}
double dinic(double mid){build(mid);double res = 0;while(bfs())memcpy(cur, head, sizeof head), res += dfs(s, inf);return res;
}
void dfs1(int u){vis[u] = 1;for(int i = head[u]; ~i; i = edges[i].nxt){int v = edges[i].v;if(vis[v] || !edges[i].c) continue;ans++, dfs1(v); }
}
int main(){//freopen("in.txt", "r", stdin);ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> m, s = 0, t = n + 1;for(int i = 0, a , b; i < m; i++){cin >> a >> b;dg[a]++, dg[b]++, es[i] = make_pair(a, b);}double l = 0, r = m;while(r - l > eps){double mid = (l + r) / 2;if(m * n  - dinic(mid) > eps) l = mid;else r = mid;}dinic(l);dfs1(s);if(!ans) cout << 1 << '\n' << 1;else{cout << ans << '\n';for(int i = 1; i <= n; i++) if(vis[i])cout << i << '\n';}return 0;
}

3.5再看最大获利

3.6.1原题链接

[P4174 NOI2006] 最大获利 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

3.6.2转化为最大密度子图问题

我们前面讲,最大密度子图由于选一个边其两个顶点都要选,所以我们把边看作点就能转化为最大密度子图问题

那么同样的,本题我们由于选一个点,另外两个点也要选,所以我们可以把用户看作连接两个中转站的边,这样我们就要求|E| + p(V)最大

而带边权点权的最大密度子图我们是最大化|E| + p(V) - g|V|,本题相当于g取0

那么我们g取0然后跑最大密度子图的板子即可

3.6.2AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5010, M = (N * 2 + 50000) << 1, inf = 1e9;
int n, m, s, t, u;
int head[N], cur[N], d[N], q[N], b, f, idx;
int dg[N], p[N];
struct edge{int v, c, nxt;
}edges[M];
void addedge(int u, int v, int c){edges[idx] = { v, c, head[u] }, head[u] = idx++;
}
void add(int u, int v, int c, int d){addedge(u, v, c), addedge(v, u, d);
}
bool bfs(){memset(d, 0, sizeof d), b = f = 0, d[q[b++] = s] = 1;while(b - f){int u = q[f++];for(int i = head[u]; ~i; i = edges[i].nxt){int v = edges[i].v;if(!d[v] && edges[i].c){d[q[b++] = v] = d[u] + 1;if(v == t) return true;}}}return false;
}
int dfs(int u, int lim){if(u == t) return lim;int res = 0;for(int i = cur[u]; ~i && lim; i = edges[i].nxt){int v = edges[i].v;cur[u] = i;if(d[v] == d[u] + 1 && edges[i].c){int incf = dfs(v, min(lim, edges[i].c));if(!incf) d[v] = 0;lim -= incf, res += incf, edges[i].c -= incf, edges[i^1].c += incf;}}return res;
}
int dinic(){int res = 0;while(bfs())memcpy(cur, head, sizeof head), res += dfs(s, inf);return res;
}
int main(){//freopen("in.txt", "r", stdin);ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> m, s = 0, t = n + 1;memset(head, -1, sizeof head);for(int i = 1; i <= n; i++) cin >> p[i], p[i] *= -1;for(int i = 0, a, b, c; i < m; i++){cin >> a >> b >> c;add(a, b, c, c), dg[a] += c, dg[b] += c;}for(int i = 1; i <= n; i++) u = max(u, dg[i] + 2 * p[i]);for(int i = 1; i <= n; i++)add(s, i, u, 0), add(i, t, u - 2 * p[i] - dg[i], 0);cout << (u * n - dinic()) / 2;return 0;
}

四、最小权点覆盖集

4.1什么是点覆盖集

给定图G(V, E),对于点集V’,原图边集E中所有边都有点在V‘内,那么我们称V’为原图G的一个点覆盖集

如果给每一个点都赋予一个权值,那么最小权点覆盖集就是所有点覆盖集中权值和最小的那个

对于一般的图而言,最小权点覆盖集问题是NP完全问题,没有多项式解。但是对于二分图的最小权点覆盖集,我们可以将其转化为最小割问题来解决。

4.2二分图的最小权点覆盖集与最小割的关系

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

对于二分图,我们这样建立流网络:

  • 源点左部点连容量为点权的有向边
  • 右部点向汇点建立容量为点权的有向边
  • 原图的边的容量设置为正无穷

下面证明:

流网络的割一定是简单割

只需证割集中没有原图的边

由于源点发出边的容量都为有限值,所以最小割也是有限值,所以割集中不包含原图容量为正无穷的边,得证。

简单割可以构造一个点覆盖集

由于简单割不包含原图的边,只需证明原图的边都至少有一个点跟源/汇点连的边在简单割中

假设存在原图的边<a,b>,a,b和源/汇点的边都不包含在割集中,那么源点和汇点就会在同一个集合中,这就不是一个割,更何况简单割,矛盾。得证

一个极小点覆盖集可以构造一个简单割

我们只考虑哪些极小点覆盖集,即任意删除一个点就不是一个点覆盖集的点覆盖集。

对于点覆盖集内的点和源/汇点的连边我们进行标记,规定从源点dfs只能沿着非标记边搜索,那么可以将原图划分为两个集合,那么源汇点一定分别处于两个集合中,否则说明从源点可以经过原图的边到达汇点,那么说明有边未覆盖,这就不是点覆盖集。矛盾,得证。

最小割的容量和就是最小权点覆盖集的权值

显然,不做证明。

4.3 POJ2125Destroying The Graph

4.3.1原题链接

2125 – Destroying The Graph (poj.org)

4.3.2思路分析

题目的意思就是对于一条有向边,我们可以通过出点删除它,那么代价就是出点的“出代价”,也可以通过入点删除它,那么代价就是入点的“入代价”,求把所有边删完的最小代价和

由于每个点都同时拥有了出点和入点的属性,那么我们自然而然地对原图拆点,就得到了左部点(入点),右部点(出点)

原图的每个点a,就变成了a+(左部点),a-(右部点),对于原图的每条边<a, b>,我们连接b+ -> a-的权值为正无穷的有向边

然后源点向每个左部点都连容量为权值的有向边,同理右部点向汇点连容量为权值的有向边

那么原问题的解就是二分的的最小割,因为最小割对应了一个最小权点覆盖集,可以通过覆盖集内的点删除掉原图的所有边

然后我们怎样去构造这样一个点覆盖集呢?

我们通过源点dfs遍历残留容量为正的边即可,遍历到的点进行标记

那么对于正向边<s, a>、<b, t>,如果残留容量为0,那么说明以a作为出点进行了删除,以b为入点进行了删除

4.3.3AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 210, M = 5200 * 2 + 10, inf = 1e9;
struct edge{int v, c, nxt;
}edges[M];
int head[N], cur[N], d[N], q[N], b, f, idx;
int n, m, s, t;
bool vis[N];
void addedge(int u, int v, int c){edges[idx].v = v, edges[idx].c = c, edges[idx].nxt = head[u], head[u] = idx++;
}
void add(int u, int v, int c){addedge(u, v, c), addedge(v, u, 0);
}
bool bfs(){memset(d, 0, sizeof d), b = f = 0, d[q[b++] = s] = 1;while(b - f){int u = q[f++];for(int i = head[u]; ~i; i = edges[i].nxt){int v = edges[i].v;if(!d[v] && edges[i].c){d[q[b++] = v] = d[u] + 1;if(v == t) return true;}}}return false;
}
int dfs(int u, int lim){if(u == t) return lim;int res = 0;for(int i = cur[u]; ~i && lim; i = edges[i].nxt){int v = edges[i].v;cur[u] = i;if(d[v] == d[u] + 1 && edges[i].c){int incf = dfs(v, min(edges[i].c, lim));if(!incf) d[v] = 0;lim -= incf, res += incf, edges[i].c -= incf, edges[i^1].c += incf;}}return res;
}
int dinic(){int res = 0;while(bfs())memcpy(cur, head, sizeof head), res += dfs(s, inf);return res;
}
void dfs1(int u){vis[u] = 1;for(int i = head[u]; ~i; i = edges[i].nxt){int v = edges[i].v;if(vis[v] || !edges[i].c) continue;dfs1(v);}
}
int main(){freopen("in.txt", "r", stdin); ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> m, s = 0, t = n * 2 + 1, memset(head, -1, sizeof head);for(int i = 1, w; i <= n; i++) cin >> w, add(s, i, w);for(int i = 1, w; i <= n; i++) cin >> w, add(i + n, t, w);for(int i = 0, a, b; i < m; i++){cin >> a >> b;add(b, a + n, inf);}cout << dinic() << '\n';dfs1(s);int cnt = 0;for(int i = 0, a, b; i < idx; i += 2){a = edges[i ^ 1].v, b = edges[i].v;cnt += (vis[a] && !vis[b]);}cout << cnt << '\n';for(int i = 0, a, b; i < idx; i += 2){a = edges[i ^ 1].v, b = edges[i].v;if(vis[a] && !vis[b])if(a == s) cout << b << " +\n";}for(int i = 0, a, b; i < idx; i += 2){a = edges[i ^ 1].v, b = edges[i].v;if(vis[a] && !vis[b])if(b == t) cout << a - n << " -\n";}return 0;
}

五、最大权独立集

5.1什么是独立集

独立集是相对于点覆盖集的一个概念。对于图G(V, E),如果点集E‘满足集合内任意两点之间没有连边,那么称点集E’为G(V, E)的一个独立集

那么最大权独立集的概念也就不言而喻了。

5.2最大权独立集和最小权点覆盖集的互补关系

原图点集V,点覆盖集V1,独立集V2,往证:V - V2是点覆盖集,V - V1是独立集

V - V2是点覆盖集

证明:假设V - V2不是点覆盖集,那么存在边<a, b>,a,b都不在V - V2中,那么a,b就在V2中,那么V2就不是独立集,矛盾,得证

V - V1是独立集

证明:假设V - V1不是独立集,那么存在边<a, b>,a,b都不在V1中,那么边<a, b>就没有被V1覆盖,V1就不是独立集。

5.3 P4474 王者之剑

5.3.1原题链接

P4474 王者之剑 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

5.3.2思路分析

性质1:我们只能在偶数秒拿钻石

如果是在奇数秒拿,那么上一秒如果是在当前格子,那么上一秒就能拿,如果上一秒是在四周,那么当前格子的钻石上一秒就会消失。

性质2:不能拿相邻钻石

因为只能在偶数秒拿,那么拿完这个其相邻的都消失了。

对于网格图建立二分图的tip:以坐标和为奇数和偶数划分为两部分,那么奇数格子只能和偶数格子互相连边。

推出:我们拿的格子构成了一个独立点集。

到这里不能想当然的认为我们的答案就是求最大权独立点集,我们还是需要证明一下独立点集和合法方案可以建立双射的。

合法方案可以构造一个独立点集

合法方案拿的格子一定是独立点集,不再赘述。

独立点集可以构造一个合法方案

我们两行两行的取。每两行奇数秒从第一行第一列开始。然后有:

  • 可以偶数秒拿完当前列
  • 如果右边第二列有宝石,可以奇数秒移动到右手边第一列,然后偶数秒拿掉右手边第二列
  • 如果右下有宝石,那么也可以奇数秒右移一格,然后偶数秒拿掉宝石
  • 由于是独立点集,每个宝石上下左右都为空,我们按照前三条规则一定能拿完点集。

那么我们对二分图建边跑最小割即可

5.3.3AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10005, M = 60010, inf = 1e9;
struct edge{int v, c, nxt;
}edges[M];
int head[N], cur[N], d[N], q[N], b, f, idx;
int n, m, s, t, tot;
int dst[5] = {1, 0, -1, 0, 1};
int getidx(int x, int y){return (x - 1) * m + y;
}
void addedge(int u, int v, int c){edges[idx] = { v, c, head[u] }, head[u] = idx++;
}
void add(int u, int v, int c){addedge(u, v, c), addedge(v, u, 0);
}
bool bfs(){memset(d, 0, sizeof d), b = f = 0, d[q[b++] = s] = 1;while(b - f){int u = q[f++];for(int i = head[u]; ~i; i = edges[i].nxt){int v = edges[i].v;if(!d[v] && edges[i].c){d[q[b++] = v] = d[u] + 1;if(v == t) return true;}}}return false;
}
int dfs(int u, int lim){if(u == t) return lim;int res = 0;for(int i = cur[u]; ~i && lim; i = edges[i].nxt){int v = edges[i].v;cur[u] = i;if(d[v] == d[u] + 1 && edges[i].c){int incf = dfs(v, min(edges[i].c, lim));if(!incf) d[v] = 0;lim -= incf, res += incf, edges[i].c -= incf, edges[i^1].c += incf;}}return res;
}
int dinic(){int res = 0;while(bfs())memcpy(cur, head, sizeof head), res += dfs(s, inf);return res;
}
int main(){//freopen("in.txt", "r", stdin);ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);memset(head, -1, sizeof head);cin >> n >> m, s = 0, t = n * m + 1;for(int i = 1, w; i <= n; i++)for(int j = 1; j <= m; j++){cin >> w, tot += w;if(i + j & 1){add(s, getidx(i, j), w);for(int k = 0; k < 4; k++){int x = i + dst[k], y = j + dst[k + 1];if(x > n || x <= 0 || y > m || y <= 0) continue;add(getidx(i, j), getidx(x, y) , inf);}}elseadd(getidx(i, j), t, w);}cout << tot - dinic();return 0;
}

六、OJ练习

6.1P2762 太空飞行计划问题

6.1.1原题链接

P2762 太空飞行计划问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

6.1.2思路分析

原图是一个二分图,左边为实验,右边为仪器

实验和所需仪器连边

实验如果想要获利,所需仪器必须都选 => 最大权闭合图问题

那么我们建图后,跑最大权闭合图的板子即可

源点向左部点连容量为点权的边,原图边容量正无穷,右部点向汇点连容量为点权的边,最大获利为实验点权和减去最小割

6.1.3AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <string>
using namespace std;
const int N = 105, M = (50 * 50 + N) << 1, inf = 1e9;
#define sc scanf
struct edge{int v, c, nxt;
}edges[M];
int head[N], cur[N], d[N], q[N], b, f, idx;
int n, m, s, t;
bool vis[N];
void addedge(int u, int v, int c){edges[idx] = { v, c, head[u] }, head[u] = idx++;
}
void add(int u, int v, int c){addedge(u, v, c), addedge(v, u, 0);
}
bool bfs(){memset(d, 0, sizeof d), b = f = 0, d[q[b++] = s] = 1;while(b - f){int u = q[f++];for(int i = head[u]; ~i; i = edges[i].nxt){int v = edges[i].v;if(!d[v] && edges[i].c){d[q[b++] = v] = d[u] + 1;if(v == t) return true;}}}return false;
}
int dfs(int u, int lim){if(u == t) return lim;int res = 0;for(int i = cur[u]; ~i && lim; i = edges[i].nxt){int v = edges[i].v;cur[u] = i;if(d[v] == d[u] + 1 && edges[i].c){int incf = dfs(v, min(lim, edges[i].c));if(!incf) d[v] = 0;res += incf, lim -= incf, edges[i].c -= incf, edges[i^1].c += incf;}}return res;
}
int dinic(){int res = 0;while(bfs())memcpy(cur, head, sizeof head), res += dfs(s, inf);return res;
}
void dfs1(int u){vis[u] = 1;for(int i = head[u]; ~i; i = edges[i].nxt){int v = edges[i].v;if(!vis[v] && edges[i].c) dfs1(v);}
}
int main(){//freopen("in.txt", "r", stdin);memset(head, -1, sizeof head);sc("%d%d", &m, &n), s = 0, t = m + n + 1;int tot = 0;getchar();for(int i = 1, w, v; i <= m; i++){string buf;getline(cin, buf);stringstream ss(buf);ss >> w, add(s, i, w), tot += w;while(ss >> v)add(i, v + m, inf);}for(int i = 1, w; i <= n; i++) sc("%d", &w), add(i + m, t, w);tot -= dinic();dfs1(s);for(int i = 1; i <= m; i ++){if(vis[i])printf("%d ", i);}puts("");for(int i = 1; i <= n; i ++){if(vis[i + m])printf("%d ", i);}printf("\n%d", tot);return 0;
}

6.2P3355 骑士共存问题

6.2.1原题链接

P3355 骑士共存问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

6.2.2思路分析

又是棋盘上的问题,可以划分为二分图

我们发现要摆放尽可能多的骑士还要让他们互相攻击不到,就等价于求最大独立点集。

对于不可放置的点我们直接从图中删去。

其它的点划分为二分图,然后左部点为奇数点,右部点为偶数点,左部点向可以攻击的右部点连容量正无穷的边。源点向左部点连容量为1的边,右部点向汇点连容量为1的边。

求最大独立点集即可。

6.2.3AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 40005, M = (20000 * 8 + 40000) << 1, inf = 1e9;
struct edge{int v, c, nxt;
}edges[M];
int n, m, s, t;
int head[N], q[N], d[N], cur[N], b, f, idx;
bool g[N][N];
int dx[8]{-1, -1, -2, -2, 1, 1, 2, 2}, dy[8]{2, -2, 1, -1, 2, -2, 1, -1};
int getidx(int x, int y){return (x - 1) * n + y;
}
void addedge(int u, int v, int c){edges[idx] = { v, c, head[u] }, head[u] = idx++;
}
void add(int u, int v, int c){addedge(u, v, c), addedge(v, u, 0);
}
bool bfs(){memset(d, 0, sizeof d), b = f = 0, d[q[b++] = s] = 1;while(b - f){int u = q[f++];for(int i = head[u]; ~i; i = edges[i].nxt){int v = edges[i].v;if(!d[v] && edges[i].c){d[q[b++] = v] = d[u] + 1;if(v == t) return true;}}} return false;
}
int dfs(int u, int lim){if(u == t) return lim;int res = 0;for(int i = cur[u]; ~i && lim; i = edges[i].nxt){int v = edges[i].v;cur[u] = i;if(d[v] == d[u] + 1 && edges[i].c){int incf = dfs(v, min(lim, edges[i].c));if(!incf) d[v] = 0;res += incf, lim -= incf, edges[i].c -= incf, edges[i^1].c += incf;}}return res;
}
int dinic(){int res = 0;while(bfs())memcpy(cur, head, sizeof head), res += dfs(s, inf);return res;
}
int main(){//freopen("in.txt", "r", stdin);ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);memset(head, -1, sizeof head);cin >> n >> m, s = 0, t = n * n + 1;for(int i = 0, a, b; i < m; i++)cin >> a >> b, g[a][b] = 1;for(int i = 1, x, y; i <= n; i++)for(int j = 1; j <= n; j++){if(g[i][j]) continue;if(i + j & 1){add(s, getidx(i, j), 1);for(int k = 0; k < 8; k++){x = i + dx[k], y = j + dy[k];if(x < 1 || y < 1 || x > n || y > n || g[x][y]) continue;add(getidx(i, j), getidx(x, y), inf);}}elseadd(getidx(i, j), t, 1);}cout << n * n - m - dinic();return 0; 
}

七、总结

最小割问题在网络流中属于一类比较抽象的问题,对于问题我们要想清楚哪些边是要割掉的,哪些点属于S,哪些点属于T,不能割掉的边如何处理,是否要拆点。随着练习量的增加,会对最小割有更深的体会。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/287800.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

ApiPost设置多人协作

有时候一个项目会有多个人一起编写&#xff0c;每个人都有自己的接口&#xff0c;ApiPost提供了一个多人协作功能&#xff0c;可以在一个项目里加入多个成员&#xff0c;每个人新增的接口都可以在项目中看到&#xff0c;从而提高开发效率。 我这边用的是ApiPost7&#xff0c;首…

深入探讨iOS开发:从创建第一个iOS程序到纯代码实现全面解析

iOS开发作为移动应用开发的重要领域之一&#xff0c;对于开发人员具有重要意义。本文将深入探讨iOS开发的各个方面&#xff0c;从创建第一个iOS程序到纯代码实现iOS开发&#xff0c;带领读者全面了解iOS应用程序的开发流程和技术要点。 &#x1f4f1; 第一个iOS程序 在创建第…

【蓝桥杯】tarjan算法

一.概述 Tarjan 算法是基于DFS的算法&#xff0c;用于求解图的连通性问题。 Tarjan 算法可以在线性时间内求出&#xff1a; 无向图&#xff1a; 割点与桥双连通分量 有向图&#xff1a; 强连通分量必经点与必经边 1.割点&#xff1a; 若从图中删除节点 x 以及所有与 x 关联的…

【c++】类和对象(四)深入了解拷贝构造函数

&#x1f525;个人主页&#xff1a;Quitecoder &#x1f525;专栏&#xff1a;c笔记仓 朋友们大家好啊&#xff0c;本篇内容带大家深入了解拷贝构造函数 目录 1.拷贝构造函数1.1传值调用的无限调用1.2浅拷贝1.3深拷贝1.4深拷贝的实现 1.拷贝构造函数 拷贝构造函数是一种特殊的…

Java版企业电子招标采购系统源码——鸿鹄电子招投标系统的技术特点

在数字化时代&#xff0c;采购管理也正经历着前所未有的变革。全过程数字化采购管理成为了企业追求高效、透明和规范的关键。该系统通过Spring Cloud、Spring Boot2、Mybatis等先进技术&#xff0c;打造了从供应商管理到采购招投标、采购合同、采购执行的全过程数字化管理。通过…

【Java面试题】计算机网络

文章目录 1.计算机网络基础1.1网络分层模型/OSI七层模型是什么&#xff1f;1.2TCP/IP四层模型是什么&#xff1f;每一层的作用&#xff1f;1.2.1TCP四层模型&#xff1f;1.2.2为什么网络要分层&#xff1f; 1.2常见网络协议1.2.1应用层常见的协议1.2.2网络层常见的协议 2.HTTP2…

解决华为云服务器宝塔面板无法访问显示“此站点的连接不安全”问题

已经配置好安全组以及初始化宝塔面板&#xff0c;还是无法访问镜像管理页面&#xff0c;提示此站点的连接不安全。 解决方案 将地址https改为http即可进入。 成功登录后&#xff0c;开启面板SSL即可。

js实现拖放效果

dataTransfer对象 说明&#xff1a;dataTransfer对象用于从被拖动元素向放置目标传递字符串数据。因为这个对象是 event 的属性&#xff0c;所以在拖放事件的事件处理程序外部无法访问 dataTransfer。在事件处理程序内部&#xff0c;可以使用这个对象的属性和方法实现拖放功能…

科学认识并正确运用人工智能技术赋能国际传播

以下文章来源&#xff1a;学习时报 加强国际传播能力建设&#xff0c;全面提升国际传播效能&#xff0c;形成同我国综合国力和国际地位相匹配的话语权&#xff0c;已成为实现中国式现代化需要解决好的一个重大问题。文生视频模型Sora&#xff0c;是继ChatGPT之后又一推动传播智…

鉴源论坛丨形式化工程方法之需求建模(下)

作者 | 杨坤 上海控安可信软件创新研究院系统建模组 版块 | 鉴源论坛 观模 引言&#xff1a;需求建模是一种从源头确保软件质量的重要手段。需求建模可分为需求规约和需求确认两个部分&#xff0c;前者通过严格设计的形式化语言精确地将需求文档转换为了形式化规约&#xff0…

手撕LRU 最近最少使用缓存淘汰策略 + LinkedHashMap

LRU 最近最少使用缓存淘汰策略 1 LRU 算法就是一种缓存淘汰策略2 手撕LRU3 LinkedHashMap 常见面试题 1 LRU 算法就是一种缓存淘汰策略 计算机的缓存容量有限&#xff0c;如果缓存满了就要删除一些内容&#xff0c;给新内容腾位置。但问题是&#xff0c;删除哪些内容呢&#x…

“Kimi概念”降温,长文本“担不起”大模型的下一步

Kimi火了…… 这是这波AI浪潮中&#xff0c;国内创业公司第一次真正“破圈”。最明显的标志是&#xff0c;在二级市场中&#xff0c;Kimi已被市场作为一个概念板块来对待&#xff0c;它们被称之为“Kimi概念股”。在之前爆炒的板块中&#xff0c;可能有华为产业链、苹果产业链&…

SV-7045VP sip网络草坪音箱 室外网络广播POE供电石头音箱

SV-7045VP sip网络草坪音箱 室外网络广播POE供电石头音箱 18123651365微信 SV-7045VP SIP网络草坪音箱 sip POE石头音箱 描述 SV-7041VP是深圳锐科达电子有限公司的一款防水网络草坪音箱&#xff0c;具有10/100M以太网接口&#xff0c;可将网络音源通过自带的功放和喇叭输出…

ESD保护二极管ESD9B3.3ST5G 以更小的空间实现强大的保护 车规级TVS二极管更给力

什么是汽车级TVS二极管&#xff1f; TVS二极管是一种用于保护电子电路的电子元件。它主要用于电路中的过电压保护&#xff0c;防止电压过高而损坏其他部件。TVS二极管通常被称为“汽车级”是因为它们能够满足汽车电子系统的特殊要求。 在汽车电子系统中&#xff0c;由于车辆启…

机器学习——神经网络简单了解

一、神经网络基本概念 神经网络可以分为生物神经网络和人工神经网络 (1)生物神经网络,指的是生物脑内的神经元、突触等构成的神经网络&#xff0c;可以使生物体产生意识&#xff0c;并协助生物体思考、行动和管理各机体活动。 (2)人工神经网络,是目前热门的深度学习的研究…

【第二部分--Python之基础】02

二、运算符与程序流程控制 1、运算符 1.1 算术运算符 算术运算符用于组织整数类型和浮点类型的数据&#xff0c;有一元运算符和二元运算符之分。 一元算术运算符有两个&#xff1a;&#xff08;正号&#xff09;和-&#xff08;负号&#xff09;&#xff0c;例如&#xff1…

【C++11】thread线程库

【C11】thread线程库 目录 【C11】thread线程库thread类的简单介绍函数指针lambda表达式常用在线程中 线程函数参数join与detach利用RAII思想来自动回收线程 原子性操作库(atomic)atomic中的load函数&#xff1a;atomic中对变量进行原子操作的一些函数 CAS(Compare-And-Swap)无…

Git学习笔记之基础

本笔记是阅读《git pro》所写&#xff0c;仅供参考。 《git pro》网址https://git-scm.com/book/en/v2 git官网 https://git-scm.com/ 一、git起步 1.1、检查配置信息 git config --list查看所有的配置以及它们所在的文件 git config --list --show-origin可能有重复的变量名…

科技云报道:从“算力核弹”到生成式AI,新纪元还有多远?

科技云报道原创。 “我们需要更大的GPU”&#xff01; 3月19日凌晨&#xff0c;一年一度的“AI风向标”重磅会议——GTC 2024如期而至。 英伟达CEO黄仁勋在大会上发布了包括新一代加速计算平台NVIDIA Blackwell、Project GR00T人形机器人基础模型、Omniverse Cloud API、NVI…

【prompt六】MaPLe: Multi-modal Prompt Learning

1.motivation 最近的CLIP适应方法学习提示作为文本输入,以微调下游任务的CLIP。使用提示来适应CLIP(语言或视觉)的单个分支中的表示是次优的,因为它不允许在下游任务上动态调整两个表示空间的灵活性。在这项工作中,我们提出了针对视觉和语言分支的多模态提示学习(MaPLe),以…