山西专业网站建设大全,seo服务方法,wordpress主题idowns,泰安网络信息有限公司文章目录 零、回顾1、流网络的割2、最小割问题 一、最小割的应用1.1POJ1966 -- Cable TV Network1.1.1原题链接1.1.2思路分析1.1.3AC代码 1.2ZOJ 2676 Network Wars1.2.1原题链接1.2.2思路分析1.2.3AC代码 1.3OPTM - Optimal Marks1.3.1原题链接1.3.2思路分析1.3.3AC代码 二、最… 文章目录 零、回顾1、流网络的割2、最小割问题 一、最小割的应用1.1POJ1966 -- Cable TV Network1.1.1原题链接1.1.2思路分析1.1.3AC代码 1.2ZOJ 2676 Network Wars1.2.1原题链接1.2.2思路分析1.2.3AC代码 1.3OPTM - Optimal Marks1.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 Life3.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 Graph4.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∈St属于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、最小割问题
最小割从定义上讲无非就是讲流网络分成分别包含源点汇点的ST两部分连接两个集合的边割去后流网络断流。
而实际应用中经常是对问题建模然后将原问题的解和最小割对应然后通过最大流算法求解最小割来求解原问题的解。
常见问题有最大权闭合子图最大密度子图最小权覆盖集最大权独立集、以及比较考验思维将问题与割相联系的问题。总之最小割问题相较于网络流问题来说更加抽象需要一定量的练习来熟悉这种建模思维。 一、最小割的应用
1.1POJ1966 – Cable TV Network
1.1.1原题链接
1966 – Cable TV Network (poj.org)
1.1.2思路分析
我们要找到使得原图不连通的最小删除点数。这个还是可以往最小割上靠的因为我们的割删除一些边使得两个集合不连通。
但是这道题删除的是点而我们割删的是边我们怎么做呢——拆点。
我们将原图每个点u拆为u和u n分别代表入点和出点入点向出点连边
一定有一个答案是删除后出现两个集合ST那么我们可以将其看作一个割割掉的点对应割掉的边即入点和出点的边
然后为了让答案和最小割联系起来对于非源点汇点的点我们从入点向出点连容量为1的边然后为了保证最小割割掉的是点即入点和出点连的边所以对于原图的其它边我们赋容量为正无穷这样最小割一定不会包含这些边
然后对于源点和汇点自然是不能割的所以其入点到出点的边的容量为正无穷
这样我们建立了一个流网络流网络的最小割对应原题的解最小割的边一定只包含入点和出点的边因为最小割有限不可能包含那些正无穷的边那么最小割就对应了一组割点集最小割是使得流网络断流的最小割而这些割边的容量是1所以就对应了割掉的点的数目所以最小割就是原题的解。
1.1.3AC代码
#include iostream
#include cstring
#include algorithm
using namespace std;
#define sc scanf
#define mkp make_pair
typedef pairint, 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最小这说明割集是有可能包含最小割中ST中的边的
所以我们该如何入手去将 c / k 最小值与最小割联系呢
我们考虑将原图每条边容量减去mid那么我们对于容量为负的边显然可以使得c / k变小换言之可以使得Σ c - mid变小所以负数边显然要选上那么对于正数边每选一条c / k都会变大所以要尽可能少选所以我们发现当我们把负数边剔除后 Σ c - mid 最小就变成了从剩下的边中挑出一些边使得原图不连通且容量和最小因为剩下的c都大于mid多选一条结果都会变大所以要尽可能少选我们发现这一部分的和就是剔除负数边后的最小割
所以对于二分答案mid Σ c - mid的最小值就是 原图每条边容量减去mid负数边直接加到答案里面然后正反边容量置为0
然后求最小割累加到答案里面就是Σ c - mid的最小值
然后check函数就写出来了二分出答案后我们还要求出割掉的边包含原图中权值的小于答案的边以及ST之间的割边
对于ST的割边直接dfs我们沿着容量不为0的边从s出发去遍历那些只有一个端点被访问的边就是最小割里的边然后权值小于答案的边我们读数据的时候就存下了所有边的权值直接找就行
1.2.3AC代码
#includeiostream
#includecstring
#includevector
#includealgorithm
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);vectorint 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位而言原图中的点可以分为两部分STS内点第i位都是1T中都是0
那么我们的贡献就是S、T之间的边因为原图任意一种划分方式都是一个割而我们建立的一个割也都对应了原图的一种划分方式而且原图的第i位的贡献对应我们S、T之间的边的容量容量为1和即最小割
那么就可以这样建模对于原图中相连的点ab我们连a-b容量为1的边以及b-a容量为1的边然后有些点是有标号的第i位为1的直接从s向其连一条正无穷的边为0的则从其向汇点连正无穷的边然后最小割就是答案
1.3.3AC代码
#includeiostream
#includecstring
#includealgorithm
using namespace std;
typedef pairint, 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每一个简单割可以构造一个闭合子图
证明 对于简单割cS, T从S - {s}中的任意一点发出的边的集合与原图边的交集的那些被边都指向S - {s}内否则就存在某条原图的边在割集内就不是简单割矛盾。所以S - {s}就是一个闭合点集 所以我们证明出了所有最小割都是简单割而且简单割和闭合子图之间的一一对应关系。
2.5利用最小割求解最大权闭合子图
我们做如下规定
对于最小割cS, T有闭合点集V‘ S - {s}记V’为V1V - 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} cS, T cs, V2 cV1, t \\ \sum_{v \in V1,w_{v} \lt 0}^{}-w_{v} \sum_{v \in V2,w_{v} \gt 0}^{}w_{v} \end{align} cS,Tcs,V2cV1,tv∈V1,wv0∑−wvv∈V2,wv0∑wv 而对于闭合子图其点权和为 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)v∈V1∑wvv∈V1,wv0∑wvv∈V1,wv0∑wv 两式相加 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) cS, 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)cS,Tv∈V1,wv0∑wvv∈V2,wv0∑wvv∈V,wv0∑wv 右边就是原图中正点权之和是一个定值
左边想要w(V1)最大那么就要最小割最小而最小割就是最小值所以w(V1)就等于原图正点权和减去最小割
2.6 练习之最大获利
2.6.1原题链接
[P4174 NOI2006] 最大获利 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
2.6.2思路分析
这个题目就很最大权闭合子图了可以说是板子题。
如果要转这个用户的收益就必须承担他要用的那些中转站的损失这不就是选这个正权点就必须把他连接的负权点也选上然后求一个最大点权和的方案不就是一个最大权闭合子图问题吗。
经过前面的推导我们发现求解方式是很简单的对于中转站向汇点连边用户则跟中转站连无穷边源点向用户连边
然后用用户收益和减去最小割就是答案
后面我们学习最大密度子图后会重看这道题
2.6.3AC代码
#includeiostream
#includecstring
#includealgorithm
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} g∣V∣−∣E∣u∈V∑g−v∈Vˉ∑(2du−2c(u,v))u∈V∑(g−2duv∈Vˉ∑2c(u,v))21u∈V∑(2g−duv∈Vˉ∑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ˉ)v∈Vˉ∑Uu∈V∑(U2g−duv∈Vˉ∑c(u,v))nUu∈V∑(2g−duv∈Vˉ∑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} ∣V∣∣E∣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} g∣V∣−p(V)−∣E∣21u∈V∑(2g−2pu−duv∈Vˉ∑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)nUu∈V∑(2g−2pu−duv∈Vˉ∑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 pairint, 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二分图的最小权点覆盖集与最小割的关系 对于二分图我们这样建立流网络
源点左部点连容量为点权的有向边右部点向汇点建立容量为点权的有向边原图的边的容量设置为正无穷
下面证明
流网络的割一定是简单割 只需证割集中没有原图的边 由于源点发出边的容量都为有限值所以最小割也是有限值所以割集中不包含原图容量为正无穷的边得证。 简单割可以构造一个点覆盖集 由于简单割不包含原图的边只需证明原图的边都至少有一个点跟源/汇点连的边在简单割中。 假设存在原图的边abab和源/汇点的边都不包含在割集中那么源点和汇点就会在同一个集合中这就不是一个割更何况简单割矛盾。得证 一个极小点覆盖集可以构造一个简单割 我们只考虑哪些极小点覆盖集即任意删除一个点就不是一个点覆盖集的点覆盖集。 对于点覆盖集内的点和源/汇点的连边我们进行标记规定从源点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, bab都不在V - V2中那么ab就在V2中那么V2就不是独立集矛盾得证
V - V1是独立集
证明假设V - V1不是独立集那么存在边a, bab都不在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不能割掉的边如何处理是否要拆点。随着练习量的增加会对最小割有更深的体会。
