最大权闭合图
0.前言参考文献：胡伯涛《最小割模型在信息学竞赛中的应用》
本文总结了上书最大权闭合图一章节核心内容及其应用。如有错误请指出。
1.最大权闭合图
对于有向图 \(G = (V,E)\) 的一个子图，如果其点集 \(V_1\) 中点的后继都还在 \(V_1\) 中，则称其为原图的一个闭合图。
而最大权闭合图即为原图所有闭合图中点权之和最大的闭合图。
根据对最大权闭合图的定义，可以发现图上的连边关系对应了各点之间的依赖性，如果要构成一个闭合图，当我们向 \(V_1\) 中加入了某个点 \(u\)，则 \(u\) 的所有出边所连向的点 \(v\) 也需要加入 \(V_1\)，这样才能保证 \(G = (V_1,E_1)\) 是一个闭合图。而对于最大权，则可以体现为最优贡献，闭合图点集中每个点根据其点权的正负大小，会对答案造成相应的正、负贡献。接下来需要考虑如何将此类问题与最大流最小割相联系。
要解决最大权闭合图一类问题，我们可以首先构造出其对应的网络 \(N = (V_N,E_N)\)：
[*]建立源点 \(s\) 与汇点 \(t\)；
[*]对于原图中的边 \((u,v)\)，建立容量为 \(+\infty\) 的有向边；
[*]对于原图中的点 \(u\)，\(w_u > 0\) 则建立 \((s,u)\) 容量为 \(w_u\)；\(w_u < 0\) 则建立 \((u,t)\) 容量为 \(-w_u\)；当 \(w_u = 0\) 时无必要。
我们使用常用的转化点权方式构造出了以上网络，考虑其有何性质。
[*]性质 1：网络 \(N\) 的最小割一定是简单割。
简单割即所有割边的一个端点为 \(s\) 或 \(t\)。因为除开与源汇相连的边，其余边的容量均为正无穷，那么最小割是肯定不会割掉这类边的。
[*]性质 2：网络 \(N\) 的闭合图与简单割一一对应：\(V_1 \cup \{s\} = S\)。
证明从略。
[*]性质 3：\(||S,T|| = \sum\limits_{u \in V_1' \and w_u > 0} w_u + \sum\limits_{u \in V_1 \and w_u < 0} (-w_u)\)
其中 \(V_1' = V - V_1\)。
因为割 \(\) 其实就是源与 \(V_1'\) 的连边与汇与 \(V_1\) 的连边，根据网络 \(N\) 的构造方式可得上式。
[*]性质 4：
\[\sum\limits_{u \in V_1} w_u = \sum\limits_{u \in V_1 \and w_u > 0} w_u - \sum\limits_{u \in V_1 \and w_u < 0} (-w_u)\\||S,T|| + \sum\limits_{u \in V_1} w_u = \sum\limits_{u \in V_1 \and w_u > 0} w_u - \sum\limits_{u \in V_1 \and w_u < 0} (-w_u) + \sum\limits_{u \in V_1' \and w_u > 0} w_u + \sum\limits_{u \in V_1 \and w_u < 0} (-w_u)\\\sum\limits_{u \in V_1} w_u = \sum\limits_{u \in V \and w_u > 0} w_u - ||S,T||\]
根据性质 4，我们可以通过计算网络 \(N\) 的最小割来计算最大权闭合图的权值。
2.例题
I.P4174 最大获利
最大权闭合图板子题。
对于一个用户群，他依赖两个中转站 \(a_i,b_i\)，开通中转站需要一定成本，这个成本就是对我们的负贡献，而开通中转站能获得一些用户群的收益，这是正贡献，据此信息建图跑最大流即可，不难通过。
#include <bits/stdc++.h>#define int long long#define ll long long#define ull unsigned long long#define db double#define ld long double#define rep(i,l,r) for (int i = (int)(l); i <= (int)(r); ++ i )#define rep1(i,l,r) for (int i = (int)(l); i >= (int)(r); -- i )#define il inline#define fst first#define snd second#define ptc putchar#define Yes ptc('Y'),ptc('e'),ptc('s'),puts("")#define No ptc('N'),ptc('o'),puts("")#define YES ptc('Y'),ptc('E'),ptc('S'),puts("")#define NO ptc('N'),ptc('O'),puts("")#define vi vector<int>#define pb emplace_back#define sz(x) (int)(x.size())#define all(x) x.begin(),x.end()#define me(a,x) memset(a,x,sizeof a)#define get(x) ((x - 1) / len + 1)#define debug() puts("------------")using namespace std;typedef pair<int,int> PII;typedef pair<int,PII> PIII;typedef pair<ll,ll> PLL;namespace szhqwq { template<class T> il void read(T &x) { x = 0; T f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); } x *= f; } template<class T,class... Args> il void read(T &x,Args &...x_) { read(x); read(x_...); } template<class T> il void print(T x) { if (x < 0) ptc('-'), x = -x; if (x > 9) print(x / 10); ptc(x % 10 + '0'); } template<class T,class T_> il void write(T x,T_ ch) { print(x); ptc(ch); } template<class T,class T_> il void chmax(T &x,T_ y) { x = x < (T)y ? (T)y : x; } template<class T,class T_> il void chmin(T &x,T_ y) { x = x > (T)y ? (T)y : x; } template<class T,class T_,class T__> il T qmi(T a,T_ b,T__ p) { T res = 1; while (b) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; } return res; } template<class T> il T gcd(T a,T b) { if (!b) return a; return gcd(b,a % b); } template<class T,class T_> il void exgcd(T a, T b, T_ &x, T_ &y) { if (b == 0) { x = 1; y = 0; return; } exgcd(b,a % b,y,x); y -= a / b * x; return ; } template<class T,class T_> il T getinv(T x,T_ p) { T inv,y; exgcd(x,(T)p,inv,y); inv = (inv + p) % p; return inv; }} using namespace szhqwq;const int N = 1e6 + 10,inf = 1e9,mod = 998244353;const ull base = 131,base_ = 233;const ll inff = 1e18;const db eps = 1e-6;int n,m,s,t;int h,cur,e,ne,idx;ll d,w,ret; bool vis;il void add(int a,int b,ll c) { e = b; w = c; ne = h; h = idx ++; return ;}il void add_edge(int a,int b,ll c) { add(a,b,c); add(b,a,0); return ;}il bool bfs() { rep(i,s,t) d = inff,cur = h,vis = 0; queue<int> q; q.push(s); d = 0; while (sz(q)) { int u = q.front(); q.pop(); for (int i = h; ~i; i = ne) { int j = e; if (w > 0 && d == inff) { d = d + 1; vis = 1; q.push(j); } } } return d < inff;}il ll dfs(int u,ll val) { if (u == t) return val; ll now = 0; for (int i = cur; ~i; i = ne) { cur = i; int j = e; if (w > 0 && d == d + 1) { ll x = dfs(j,min(w,val - now)); if (x <= 0) continue; now += x; w -= x; w += x; if (now == val) return now; } } return now;}il void Dinic() { ret = 0; while (bfs()) ret += dfs(s,inff); return ;}il void solve() { //------------code------------ read(n,m); s = 0,t = n + m + 1; me(h,-1); rep(i,1,n) { int p; read(p); add_edge(i + m,t,p); } ll sum = 0; rep(i,1,m) { int a,b,c; read(a,b,c); add_edge(s,i,c); add_edge(i,a + m,inf); add_edge(i,b + m,inf); sum += c; } Dinic(); write(sum - ret,'\n'); return ;}il void init() { return ;}signed main() { // init(); int _ = 1; // read(_); while (_ -- ) solve(); return 0;}II.P2762 太空飞行计划问题
此题不仅需要求出最大权闭合图的最大权，还需要输出相应方案。
根据性质 3，不难发现网络上割掉的边（满流的边）即为 \(V_1\) 中的负贡献点向汇的连边以及 \(V_1\) 补集中正贡献点向源的连边。实际上对于割 \(\)，我们的方案就是集合 \(S - \{s\} = V_1\)。
这一点体现在代码上就是在我们不能再继续增广的时候最后一遍 bfs 分层参与分层的点即为 \(S\) 集合中的点。所以做完 Dinic 后直接判断当前点是否参与分层就能输出方案。
这个题输入格式比较难受。
#include <bits/stdc++.h>#define int long long#define ll long long#define ull unsigned long long#define rep(i,l,r) for (int i = (int)(l); i <= (int)(r); ++ i )#define rep1(i,l,r) for (int i = (int)(l); i >= (int)(r); -- i )#define il inline#define fst first#define snd second#define ptc putchar#define Yes ptc('Y'),ptc('e'),ptc('s'),puts("")#define No ptc('N'),ptc('o'),puts("")#define YES ptc('Y'),ptc('E'),ptc('S'),puts("")#define NO ptc('N'),ptc('O'),puts("")#define pb emplace_back#define sz(x) (int)(x.size())#define all(x) x.begin(),x.end()#define debug() puts("------------------")using namespace std;typedef pair<int,int> PII;typedef pair<int,PII> PIII;namespace szhqwq { template<class T> il void read(T &x) { x = 0; T f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); } x *= f; } template<class T,class... Args> il void read(T &x,Args &...x_) { read(x); read(x_...); } template<class T> il void print(T x) { if (x < 0) ptc('-'), x = -x; if (x > 9) print(x / 10); ptc(x % 10 + '0'); } template<class T,class T_> il void write(T x,T_ ch) { print(x); ptc(ch); } template<class T,class T_> il void chmax(T &x,T_ y) { x = max(x,y); } template<class T,class T_> il void chmin(T &x,T_ y) { x = min(x,y); } template<class T,class T_,class T__> il T qmi(T a,T_ b,T__ p) { T res = 1; while (b) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; } return res; } template<class T> il int getinv(T x,T p) { return qmi(x,p - 2,p); }} using namespace szhqwq;const int N = 6e6 + 10,inf = 1e9,mod = 998244353;const ll inff = 1e18;int n,m,s,t;int h,e,ne,idx;ll d,w;bool vis;int cur;ll res;int nail;string str;int read(){ if(nail>=str.size())return 0; int b=0; while(nail<str.size() and (str<'0' or str>'9'))nail++; while(nail<str.size() and str>='0' and str<='9'){ b=b*10+str-'0'; nail++; } return b;}il void add(int a,int b,ll c) { e = b; w = c; ne = h; h = idx ++;}il void add_edge(int a,int b,ll c) { add(a,b,c); add(b,a,0);}il bool bfs() { rep(i,s,t) vis = 0,d = inff,cur = h; queue<int> q; q.push(s); vis = 1; d = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = h; ~i; i = ne) { int j = e; if (d + 1 < d && w) { d = d + 1; if (!vis) { vis = 1; q.push(j); } } } } if (d == inff) return 0; return 1;}il ll dfs(int u,ll val) { if (u == t) { res += val; return val; } ll now = 0; for (int i = cur; ~i; i = ne) { cur = i; int j = e; if (d == d + 1 && w) { ll x = dfs(j,min(w,val - now)); // if (!x) d = -1; if (x) { now += x; w -= x; w += x; if (now == val) break; } } } return now;}il void Dinic() { while (bfs()) dfs(s,inff);}il void solve() { //------------code------------ memset(h,-1,sizeof h); cin >> m >> n; int sum = 0; s = 0,t = 10002; getline(cin,str); rep(i,1,m) { nail = 0; getline(cin,str); int x; x = read(); sum += x; add_edge(s,i,x); int y; while(1){ y = read(); if(!y) break; add_edge(i,y + m,inff); } } rep(i,1,n) { int x; cin >> x; add_edge(m + i,t,x); } Dinic(); rep(i,1,m) if(d != inff) printf("%lld ",i); puts(""); rep(i,1,n) if(d != inff) printf("%lld ",i); puts(""); printf("%lld",sum - res); return ;}il void init() { return ;}signed main() { // init(); int _ = 1; // read(_); while (_ -- ) solve(); return 0;}3.练习题
其实是个变式。
III.AT_arc085_c MUL
要求最小权闭合图，所以边权取反后做最大权闭合图即可。
#include <bits/stdc++.h>#define int long long#define ll long long#define ull unsigned long long#define db double#define ld long double#define rep(i,l,r) for (int i = (int)(l); i <= (int)(r); ++ i )#define rep1(i,l,r) for (int i = (int)(l); i >= (int)(r); -- i )#define il inline#define fst first#define snd second#define ptc putchar#define Yes ptc('Y'),ptc('e'),ptc('s'),puts("")#define No ptc('N'),ptc('o'),puts("")#define YES ptc('Y'),ptc('E'),ptc('S'),puts("")#define NO ptc('N'),ptc('O'),puts("")#define vi vector<int>#define pb emplace_back#define sz(x) (int)(x.size())#define all(x) x.begin(),x.end()#define me(a,x) memset(a,x,sizeof a)#define get(x) ((x - 1) / len + 1)#define debug() puts("------------")using namespace std;typedef pair<int,int> PII;typedef pair<int,PII> PIII;typedef pair<ll,ll> PLL;namespace szhqwq { template<class T> il void read(T &x) { x = 0; T f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); } x *= f; } template<class T,class... Args> il void read(T &x,Args &...x_) { read(x); read(x_...); } template<class T> il void print(T x) { if (x < 0) ptc('-'), x = -x; if (x > 9) print(x / 10); ptc(x % 10 + '0'); } template<class T,class T_> il void write(T x,T_ ch) { print(x); ptc(ch); } template<class T,class T_> il void chmax(T &x,T_ y) { x = x < (T)y ? (T)y : x; } template<class T,class T_> il void chmin(T &x,T_ y) { x = x > (T)y ? (T)y : x; } template<class T,class T_,class T__> il T qmi(T a,T_ b,T__ p) { T res = 1; while (b) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; } return res; } template<class T> il T gcd(T a,T b) { if (!b) return a; return gcd(b,a % b); } template<class T,class T_> il void exgcd(T a, T b, T_ &x, T_ &y) { if (b == 0) { x = 1; y = 0; return; } exgcd(b,a % b,y,x); y -= a / b * x; return ; } template<class T,class T_> il T getinv(T x,T_ p) { T inv,y; exgcd(x,(T)p,inv,y); inv = (inv + p) % p; return inv; }} using namespace szhqwq;const int N = 2e5 + 10,inf = 1e9,mod = 998244353;const ull base = 131,base_ = 233;const ll inff = 1e18;const db eps = 1e-6;int n,m,s,t,a;int h,cur,e,ne,idx;ll d,w,ret; bool vis;il void add(int a,int b,ll c) { e = b; w = c; ne = h; h = idx ++; return ;}il void add_edge(int a,int b,ll c) { add(a,b,c); add(b,a,0); return ;}il bool bfs() { rep(i,s,t) d = inf,cur = h,vis = 0; queue<int> q; q.push(s); d = 0; while (sz(q)) { int u = q.front(); q.pop(); for (int i = h; ~i; i = ne) { int j = e; if (w > 0 && d == inf) { d = d + 1; vis = 1; q.push(j); } } } return d != inf;}il ll dfs(int u,ll val) { if (u == t) return val; ll now = 0; for (int i = cur; ~i; i = ne) { cur = i; int j = e; if (w > 0 && d == d + 1) { ll x = dfs(j,min(w,val - now)); if (x <= 0) continue; now += x; w -= x; w += x; if (now == val) return now; } } return now;}il void Dinic() { ret = 0; while (bfs()) ret += dfs(s,inff); return ;}il void solve() { //------------code------------ read(n); s = 0,t = n + 1; me(h,-1); rep(i,1,n) for (int x = i * 2; x <= n; x += i ) add_edge(i,x,inff); ll sum = 0; rep(i,1,n) { read(a); if (a < 0) add_edge(s,i,-a); else add_edge(i,t,a); sum += max(a,0ll); } Dinic(); write(sum - ret,'\n'); return ;}il void init() { return ;}signed main() { // init(); int _ = 1; // read(_); while (_ -- ) solve(); return 0;}完结撒花 111。
页:
[1]