wordpress搭建企业网站,小型网络架构,网站自助建设平台有哪些,怎样选择网站建设最大权闭合子图和最大密度子图最大权闭合子图contentexercise最大密度子图contentexerciseUpd#xff1a;最大权闭合子图易懂证明最大权闭合子图
content
先作出以下声明#xff1a; c(u,v):c(u,v):c(u,v): 边 (u,v)(u,v)(u,v) 的容量。 f(u,v):f(u,v):f(u,v): 边 (u,v)(u,…
最大权闭合子图和最大密度子图最大权闭合子图contentexercise最大密度子图contentexerciseUpd最大权闭合子图易懂证明最大权闭合子图
content
先作出以下声明
c(u,v):c(u,v):c(u,v): 边 (u,v)(u,v)(u,v) 的容量。
f(u,v):f(u,v):f(u,v): 边 (u,v)(u,v)(u,v) 的流量。
[S,T]:[S,T]:[S,T]: 符号表示一个边集 {(u,v)∣(u,v)∈E,u∈S,v∈T}\Big\{(u,v)\ \Big |\ (u,v)\in E,u\in S,v\in T\Big\}{(u,v) ∣∣∣ (u,v)∈E,u∈S,v∈T}。
c[S,T]:c[S,T]:c[S,T]: 将流网络 G(V,E)G(V,E)G(V,E) 的点集划分成 S,T(STV)S,T(STV)S,T(STV) 两个完全不交的部分源 s∈Ss\in Ss∈S汇 t∈Tt\in Tt∈T的割的容量。
容量最小的割即为一个网络的最小割。 问题引入 一个有向图 G(V,E)G(V,E)G(V,E) 的闭合图 G′(V′,E′)G(V,E)G′(V′,E′) 是原图的一个点集且该点集的所有出边仍指向该点集。 即 ∀(u,v)∈E,u∈V′⇒v∈V′\forall_{(u,v)\in E},u\in V\Rightarrow v\in V∀(u,v)∈E,u∈V′⇒v∈V′。 给每个点定义一个点权 www最大权闭合图就是权和最大的闭合图即最大化 ∑v∈V′wv\sum_{v\in V}w_v∑v∈V′wv。 利用网络流的最小割进行快速求解形式化的建图如下
将图转化为网络 N(VN,EN)N(V_N,E_N)N(VN,EN)添入源点汇点 s,ts,ts,t。 {VNV⋃{s,t}ENE⋃{e(s,v)∣v∈V,wv0}⋃{e(v,t)∣v∈V,wv0}c(u,v)∞e(u,v)∈Ec(s,v)wvwv0c(v,t)−wvwv0\begin{cases} V_NV\bigcup \{s,t\}\\ E_NE\bigcup \{e(s,v)|v\in V,w_v0\}\bigcup\{e(v,t)|v\in V,w_v0\}\\ c(u,v)∞\quad\quad e(u,v)\in E\\ c(s,v)w_v\quad \quad w_v0\\ c(v,t)-w_v\quad\ w_v0 \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧VNV⋃{s,t}ENE⋃{e(s,v)∣v∈V,wv0}⋃{e(v,t)∣v∈V,wv0}c(u,v)∞e(u,v)∈Ec(s,v)wvwv0c(v,t)−wv wv0 定义若一个 s−ts-ts−t 割满足割中每条边都只与源点或汇点相连则称该割为简单割。
根据定义可得网络 NNN 的简单割是不含原图 GGG 中边集 EEE 的任意一条边的。 引理1 网络 NNN 的最小割是简单割。 证明 网络 NNN 的边分为与源或汇关联容量有限和不与源汇关联原边集 EEE 中所有边容量无限的两种。 所有与源或汇关联的边组成的割集的容量是有限的为所有点权的绝对值和。 最小割容量也至多为该绝对值和。 故最小割不可能取任何容量为正无限的边即最小割是简单割。
作出以下声明
记简单割 [S,T][S,T][S,T] 将网络 NNN 的点集 VNV_NVN 划分为点集 SSS 及其补集 T(TVN−S)T(TV_N-S)T(TVN−S)且 s∈S,t∈Ts\in S,t\in Ts∈S,t∈T。
设闭合图为 V1V_1V1则其在 VVV 中补集为 V1ˉ\bar{V_1}V1ˉ。
记 VV^V 为 VVV 中点权为正的点集V−V^-V− 为 VVV 中点权为负的点集。
同样可以这么定义 V1,V1−,V1ˉ,V1ˉ−V_1^,V_1^-,\bar{V_1}^,\bar{V_1}^-V1,V1−,V1ˉ,V1ˉ−。 引理2 网络 NNN 的简单割 [S,T][S,T][S,T] 与图 GGG 的闭合图 V1V_1V1 存在一一对应的关系。 即 V1⋃{s}SV_1\bigcup \{s\}SV1⋃{s}S。 证明 闭合图对应简单割即 SV1⋃{s},V1ˉ⋃{t}SV_1\bigcup\{s\},\bar{V_1}\bigcup\{t\}SV1⋃{s},V1ˉ⋃{t}。 反证法。若存在 (u,v)∈E,u∈S−{s}V1,v∈T−{t}V1ˉ(u,v)\in E,u\in S-\{s\}V_1,v\in T-\{t\}\bar{V_1}(u,v)∈E,u∈S−{s}V1,v∈T−{t}V1ˉ使得 [S,T][S,T][S,T] 含不与源汇关联的边。则闭合图 V1V_1V1 有一个后继不在闭合图内矛盾。 简单割对应闭合图即 V1S−{s}V_1S-\{s\}V1S−{s} 是闭合图。 对于闭合图中 ∀u∈V1\forall_{u\in V_1}∀u∈V1考虑任意一条由 uuu 引出的边 (u,v)∈E(u,v)\in E(u,v)∈E由于简单割 [S,T][S,T][S,T] 不含 EEE 中任意一条边所以 v≠T−{t}V1ˉv\neq T-\{t\}\bar{V_1}vT−{t}V1ˉ。即 v∈V1v\in V_1v∈V1符合闭合图定义。 推论 c[S,T]∑v∈V1ˉwv∑v∈V1−(−wv)c[S,T]\sum_{v\in \bar{V_1}^}w_v\sum_{v\in V_1^-}(-w_v)c[S,T]v∈V1ˉ∑wvv∈V1−∑(−wv) 证明 可以将割 [S,T][S,T][S,T] 按照与源汇的关联分为三个部分:[S,T][{s},V1ˉ]⋃[{t},V1]⋃[V1,V1ˉ]:[S,T][\{s\},\bar{V_1}]\bigcup[\{t\},V_1]\bigcup[V_1,\bar{V_1}]:[S,T][{s},V1ˉ]⋃[{t},V1]⋃[V1,V1ˉ]。 由于 [S,T][S,T][S,T] 是简单割所以 [V1,V1ˉ]∅V_1,\bar{V_1}]\emptyV1,V1ˉ]∅。 因为源只与点权为正的点相连所以 [{s},V1ˉ][{s},V1ˉ][\{s\},\bar{V_1}][\{s\},\bar{V_1}^][{s},V1ˉ][{s},V1ˉ]。 因为汇只与点权为负的点相连所以 [{t},V1][{t},V1−][\{t\},V_1][\{t\},V_1^-][{t},V1][{t},V1−]。 定理 当网络 NNN 取最小割时对应的闭合图达到最大权。 证明 按照定义闭合图的权和可以表示为∑v∈V1wv−∑v∈V1−(−wv)\sum_{v\in V_1^}w_v-\sum_{v\in V_1^-}(-w_v)∑v∈V1wv−∑v∈V1−(−wv)。 w(V1)c[S,T]∑v∈V1wv−∑v∈V1−(−wv)∑v∈V1ˉwv∑v∈V1−(−wv)w(V_1)c[S,T]\sum_{v\in V_1^}w_v-\sum_{v\in V_1^-}(-w_v)\sum_{v\in \bar{V_1}^}w_v\sum_{v\in V_1^-}(-w_v)w(V1)c[S,T]v∈V1∑wv−v∈V1−∑(−wv)v∈V1ˉ∑wvv∈V1−∑(−wv)∑v∈V1wv∑v∈V1ˉwv∑v∈Vwv\sum_{v\in V_1^}w_v\sum_{v\in \bar{V_1}^}w_v\sum_{v\in V^}w_v v∈V1∑wvv∈V1ˉ∑wvv∈V∑wv 即 w(V1)∑v∈Vwv−c[S,T]w(V_1)\sum_{v\in V^}w_v-c[S,T]w(V1)∑v∈Vwv−c[S,T]。 因为 ∑v∈Vwv\sum_{v\in V^}w_v∑v∈Vwv 是原图 GGG 中所有正权点之和是常数。 所以最大化闭合图权和就得最小化简单割的容量而最小割是简单割。得证。
复杂度就是求最小割的复杂度。
exercise
[NOI2006]最大获利
#include bits/stdc.h
using namespace std;
#define maxn 60005
#define inf 0x7f7f7f7f
queue int q;
struct node { int to, nxt, flow; }E[maxn 3];
int head[maxn], cur[maxn], dep[maxn];
int n, m, s, t, cnt;int read() {int x 0; char s getchar();while( s 0 or s 9 ) s getchar();while( 0 s and s 9 ) {x ( x 1 ) ( x 3 ) ( s ^ 48 );s getchar();}return x;
}bool bfs() {memset( dep, 0, sizeof( dep ) );dep[s] 1; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i cur[u] head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dep[v] and E[i].flow ) {dep[v] dep[u] 1;q.push( v );}}}return dep[t];
}int dfs( int u, int cap ) {if( u t or ! cap ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {cur[u] i; int v E[i].to;if( dep[v] dep[u] 1 ) {int w dfs( v, min( cap, E[i].flow ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}int dinic() {int ans 0;while( bfs() ) ans dfs( s, inf );return ans;
}int id( int x, int y ) { return ( x - 1 ) * m y; }bool inside( int x, int y ) {if( x 1 or x n or y 1 or y m ) return 0;return 1;
}void addedge( int u, int v, int w ) {E[cnt] { v, head[u], w };head[u] cnt ;E[cnt] { u, head[v], 0 };head[v] cnt ;
}int main() {memset( head, -1, sizeof( head ) );scanf( %d %d, n, m );s 0, t n m 1;int sum 0;for( int i 1, x;i n;i )addedge( s, i, x read() );for( int i 1;i m;i ) {int a read(), b read(), c read();addedge( a, i n, inf );addedge( b, i n, inf );addedge( i n, t, c );sum c;}sum - dinic();printf( %d\n, sum );return 0;
}最大密度子图
content 问题引入 给定一张图 G(V,E)G(V,E)G(V,E)从中选一个子图 G′(V′,E′)G(V,E)G′(V′,E′) 使得其密度 D∣E′∣∣V′∣D\frac{|E|}{|V|}D∣V′∣∣E′∣ 最大。最大化并输出这个 DDD。 重新函数化上述式子Df(x)∑e∈Exe∑v∈Vxv,x∈{0,1}Df(x)\frac{\sum_{e\in E}x_e}{\sum_{v\in V}x_v},x\in\{0,1\}Df(x)∑v∈Vxv∑e∈Exe,x∈{0,1}。
以下简记 ∣V∣n,∣E∣m|V|n,|E|m∣V∣n,∣E∣m。
这个式子跟 0/1分数规划 有着异曲同工之妙。
同样考虑二分结果 ggg。
记h(g)maxx{∑e∈Exe−∑v∈Vxv∗g}h(g)\max_x\Big\{\sum_{e\in E}x_e-\sum_{v\in V}x_v*g\Big\}h(g)maxx{∑e∈Exe−∑v∈Vxv∗g}。
记问题最终答案为 ansansans则 ∀G′(n,m)mn≤ans\forall_{G(n,m)}\frac{m}{n}\le ans∀G′(n,m)nm≤ans。 {h(g)0⇒gansh(g)0⇒gansh(g)0⇒gans\begin{cases} h(g)0\Rightarrow gans\\ h(g)0\Rightarrow gans\\ h(g)0\Rightarrow gans \end{cases} ⎩⎪⎨⎪⎧h(g)0⇒gansh(g)0⇒gansh(g)0⇒gans 确定二分查找范围[1n,m1][\frac{1}{n},\frac{m}{1}][n1,1m]。
确定精度误差1n2\frac{1}{n^2}n21。 引理1 无向图 GGG 中任意两个具有不同密度的子图 G1,G2G_1,G_2G1,G2其密度差不小于 1n2\frac{1}{n^2}n21。 证明 不妨假设 G1G_1G1 子图的密度大于 G2G_2G2 子图的密度。 m1n1−m2n2m1n2−m2n1n1n2≥1n1n2≥1n2\frac{m_1}{n_1}-\frac{m_2}{n_2}\frac{m_1n_2-m_2n_1}{n_1n_2}\ge \frac{1}{n_1n_2}\ge\frac{1}{n^2}n1m1−n2m2n1n2m1n2−m2n1≥n1n21≥n21 推论 对于无向图 GGG 而言如果存在密度为 DDD 的子图 G′GG′且不存在密度 ≥D\ge D≥D 的子图则 G′GG′ 为最大密度子图。 接下来考虑如何求解二分答案对应的最大子图密度值 h(g)h(g)h(g)。 引理2 当点集确定时点集的诱导子图一定是最优解。 诱导子图从原图 GV,EGV,EGV,E 中选出一个子图 G′(V′,E′)G(V,E)G′(V′,E′)∀u,v∈V′\forall_{u,v\in V}∀u,v∈V′ 必有 e(u,v)∈E′e(u,v)\in Ee(u,v)∈E′即全选子图点集内部的边。 考虑假设点集被确定为 V′VV′如何继续求解子图 G′(V′,E′)G(V,E)G′(V′,E′)。
正向思维就是直接把点集中两两点之间的边选出来。但这里我们不采取这样的做法因为暴力无法优化。
考虑逆向思维将与点集 V′VV′ 相关的所有边集去除掉不是 E′EE′ 中的边集。
具体而言用 ∑v∈V′dv−\sum_{v\in V}d_v-∑v∈V′dv− 红色边再除以 222di:id_i:idi:i 点的度数。除以 222 是因为 EEE 的边被两个端点都算了一次。 红色边的图上意义就是连接 VVV 和 V−V′V-VV−V′ 两个完全不交的点集的边。
这就有一种「割」的意味了。
由于是要最大化 ∣E′∣−g⋅∣V′∣|E|-g·|V|∣E′∣−g⋅∣V′∣乘以 −1-1−1 转化为最小化 g⋅∣V′∣−∣E′∣g·|V|-|E|g⋅∣V′∣−∣E′∣。
g⋅∣V′∣−∣E′∣∑v∈V′g−∑e∈E′1∑v∈V′g−∑v∈V′dv−c[V′,V−V′]2g·|V|-|E|\sum_{v\in V}g-\sum_{e\in E}1\sum_{v\in V}g-\frac{\sum_{v\in V}d_v-c[V,V-V]}{2}g⋅∣V′∣−∣E′∣v∈V′∑g−e∈E′∑1v∈V′∑g−2∑v∈V′dv−c[V′,V−V′]12(∑v∈V′(2g−dv)c[V′,V−V′])\frac{1}{2}\Big(\sum_{v\in V}(2g-d_v)c[V,V-V]\Big)21(v∈V′∑(2g−dv)c[V′,V−V′])
∑v∈V′(2g−dv)\sum_{v\in V}(2g-d_v)∑v∈V′(2g−dv)就是选了 vvv就要花费代价 2g−dv2g-d_v2g−dv 这相当于每个点多了个 2g−dv2g-d_v2g−dv 的点权。
常见处理让 V′VV′ 中的点都与 ttt 相连把点权赋成边权。
由于最小割只接受非负边权但点权可能为负数那么就把所有边权都加上一个极大值 BigBigBig保证非负最后再减去即可。
总结形式化地将图 G(V,E)G(V,E)G(V,E) 转化为网络 N(VN,EN)N(V_N,E_N)N(VN,EN) {VNV⋃{s,t}EN{(u,v)∣(u,v)∈E}⋃{(s,v)∣v∈V}⋃{(v,t)∣v∈V}c(u,v)1(u,v)∈Ec(s,v)Bigv∈Vc(v,t)Big2g−dvv∈V\begin{cases}V_NV\bigcup\{s,t\}\\E_N\{(u,v)|(u,v)\in E\}\bigcup\{(s,v)|v\in V\}\bigcup\{(v,t)|v\in V\}\\c(u,v)1\quad\quad\quad\quad\quad\quad(u,v)\in E\\c(s,v)Big\quad\quad\quad\quad\quad\ v\in V\\c(v,t)Big2g-d_v\quad v\in V\end{cases} ⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧VNV⋃{s,t}EN{(u,v)∣(u,v)∈E}⋃{(s,v)∣v∈V}⋃{(v,t)∣v∈V}c(u,v)1(u,v)∈Ec(s,v)Big v∈Vc(v,t)Big2g−dvv∈V 引理3 网络 NNN 的一个割 [S,T][S,T][S,T] 与原图 GGG 的子图 G′(V′,E′)G(V,E)G′(V′,E′) 方案存在一一对应关系。即 V′⋃{s}SV\bigcup\{s\}SV′⋃{s}S。 因为割可以是任意划分的子图也可以是任意划分的。 定理 网络 NNN 的一个最小割 [S,T][S,T][S,T] 其根据 引理2 所对应子图 G′GG′ 是 h(g)h(g)h(g) 的一个最优解。 证明 设 c[S,T]c[S,T]c[S,T] 为网络 NNN 的任意一个割的容量。根据 引理3 V’S−{s},V′ˉT−{t}V’S-\{s\},\bar{V}T-\{t\}V’S−{s},V′ˉT−{t}。 c[S,T]∑u∈S,v∈Tc(u,v)∑v∈V′ˉc(s,v)∑v∈V′c(v,t)∑u∈V′,v∈V′ˉ,(u,v)∈Ec(u,v)c[S,T]\sum_{u\in S,v\in T}c(u,v)\sum_{v\in \bar{V}}c(s,v)\sum_{v\in V}c(v,t)\sum_{u\in V,v\in \bar{V},(u,v)\in E}c(u,v)c[S,T]u∈S,v∈T∑c(u,v)v∈V′ˉ∑c(s,v)v∈V′∑c(v,t)u∈V′,v∈V′ˉ,(u,v)∈E∑c(u,v)∑v∈V′ˉBig∑v∈V′Big2g−dv∑u∈V′,v∈V′ˉ,(u,v)∈E1\sum_{v\in \bar{V}}Big\sum_{v\in V}Big2g-d_v\sum_{u\in V,v\in \bar{V},(u,v)\in E}1v∈V′ˉ∑Bigv∈V′∑Big2g−dvu∈V′,v∈V′ˉ,(u,v)∈E∑1Big⋅∣V∣∑u∈V′(2g−du∑v∈V′ˉ,(u,v)∈E1)Big·|V|\sum_{u\in V}\Big(2g-d_u\sum_{v\in \bar{V},(u,v)\in E}1\Big)Big⋅∣V∣u∈V′∑(2g−duv∈V′ˉ,(u,v)∈E∑1)Big⋅∣V∣∑u∈V′(2g−∑v∈V′,(u,v)∈E1)Big·|V|\sum_{u\in V}\Big(2g-\sum_{v\in V,(u,v)\in E}1\Big)Big⋅∣V∣u∈V′∑(2g−v∈V′,(u,v)∈E∑1)Big∗n2g∣V′∣−2∣E′∣Big*n2g|V|-2|E|Big∗n2g∣V′∣−2∣E′∣U∗n−2(∣E′∣−g∣V′∣)U*n-2(|E|-g|V|) U∗n−2(∣E′∣−g∣V′∣) E′EE′ 已重定义为 V′VV′ 的导出子图的边集。 U∗nU*nU∗n 为定值当割取最小的时候2(∣E′∣−g∣V′∣)2(|E|-g|V|)2(∣E′∣−g∣V′∣) 取最大。即 h(g)U∗n−c[S,T]2h(g)\frac{U*n-c[S,T]}{2}h(g)2U∗n−c[S,T]其中 [S,T][S,T][S,T] 为最小割。
参考选摘胡伯涛《最小割模型在信息学竞赛中的应用》
exercise
UVA Hard Life
#include queue
#include cstdio
#include cstring
#include iostream
using namespace std;
#define maxn 100005
struct node { int to, nxt; double flow; }E[maxn];
struct Node { int u, v; }edge[maxn];
queue int q;
int n, m, s, t, cnt;
int head[maxn], cur[maxn], dep[maxn], d[maxn];
bool vis[maxn];void addedge( int u, int v, double w1, double w2 ) {E[cnt] { v, head[u], w1 };head[u] cnt ;E[cnt] { u, head[v], w2 };head[v] cnt ;
}void build( double g ) {memset( head, -1, sizeof( head ) ); cnt 0;for( int i 1;i m;i ) addedge( edge[i].u, edge[i].v, 1, 1 );for( int i 1;i n;i ) addedge( s, i, m, 0 ), addedge( i, t, m 2 * g - d[i], 0 );
}bool bfs() {memset( dep, 0, sizeof( dep ) );dep[s] 1; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i cur[u] head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dep[v] and E[i].flow 0 ) {dep[v] dep[u] 1;q.push( v );}}}return dep[t];
}double dfs( int u, double cap ) {if( u t or cap 0 ) return cap;double flow 0;for( int i cur[u];~ i;i E[i].nxt ) {cur[u] i; int v E[i].to;if( dep[v] dep[u] 1 ) {double w dfs( v, min( cap, E[i].flow ) );if( w 0 ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( cap 0 ) break;}}return flow;
}double dinic( double g ) {build( g );double ans 0;while( bfs() ) ans dfs( s, 2e9 );return ans;
}void dfs( int now ) {if( vis[now] ) return;vis[now] 1;if( now ^ s ) cnt ;for( int i head[now];~ i;i E[i].nxt )if( E[i].flow 0 ) dfs( E[i].to );
}int main() {while( ~ scanf( %d %d, n, m ) ) {s 0, t n 1;for( int i 0;i n;i ) vis[i] d[i] 0;for( int i 1, u, v;i m;i ) {scanf( %d %d, u, v );edge[i] { u, v };d[u] , d[v] ;}double l 0, r m, eps 1.0 / double(n * n);while( r - l eps ) {double mid ( l r ) / 2;if( m * n - dinic( mid ) eps ) l mid;else r mid;}dinic( l );cnt 0;dfs( s );if( ! cnt ) printf( 1\n1\n );else {printf( %d\n, cnt );for( int i 1;i n;i )if( vis[i] ) printf( %d\n, i );}}return 0;
}Upd最大权闭合子图易懂证明
