最大權(quán)閉合圖
0.前言
參考文獻(xiàn)：胡伯濤《最小割模型在信息學(xué)競(jìng)賽中的應(yīng)用》
本文總結(jié)了上書最大權(quán)閉合圖一章節(jié)核心內(nèi)容及其應(yīng)用。如有錯(cuò)誤請(qǐng)指出。
1.最大權(quán)閉合圖
對(duì)于有向圖 \(G = (V,E)\) 的一個(gè)子圖，如果其點(diǎn)集 \(V_1\) 中點(diǎn)的后繼都還在 \(V_1\) 中，則稱其為原圖的一個(gè)閉合圖。
而最大權(quán)閉合圖即為原圖所有閉合圖中點(diǎn)權(quán)之和最大的閉合圖。
根據(jù)對(duì)最大權(quán)閉合圖的定義，可以發(fā)現(xiàn)圖上的連邊關(guān)系對(duì)應(yīng)了各點(diǎn)之間的依賴性，如果要構(gòu)成一個(gè)閉合圖，當(dāng)我們向 \(V_1\) 中加入了某個(gè)點(diǎn) \(u\)，則 \(u\) 的所有出邊所連向的點(diǎn) \(v\) 也需要加入 \(V_1\)，這樣才能保證 \(G = (V_1,E_1)\) 是一個(gè)閉合圖。而對(duì)于最大權(quán)，則可以體現(xiàn)為最優(yōu)貢獻(xiàn)，閉合圖點(diǎn)集中每個(gè)點(diǎn)根據(jù)其點(diǎn)權(quán)的正負(fù)大小，會(huì)對(duì)答案造成相應(yīng)的正、負(fù)貢獻(xiàn)。接下來(lái)需要考慮如何將此類問題與最大流最小割相聯(lián)系。
要解決最大權(quán)閉合圖一類問題，我們可以首先構(gòu)造出其對(duì)應(yīng)的網(wǎng)絡(luò) \(N = (V_N,E_N)\)：
- 建立源點(diǎn) \(s\) 與匯點(diǎn) \(t\)；
- 對(duì)于原圖中的邊 \((u,v)\)，建立容量為 \(+\infty\) 的有向邊；
- 對(duì)于原圖中的點(diǎn) \(u\)，\(w_u > 0\) 則建立 \((s,u)\) 容量為 \(w_u\)；\(w_u < 0\) 則建立 \((u,t)\) 容量為 \(-w_u\)；當(dāng) \(w_u = 0\) 時(shí)無(wú)必要。
我們使用常用的轉(zhuǎn)化點(diǎn)權(quán)方式構(gòu)造出了以上網(wǎng)絡(luò)，考慮其有何性質(zhì)。
- 性質(zhì) 1：網(wǎng)絡(luò) \(N\) 的最小割一定是簡(jiǎn)單割。
簡(jiǎn)單割即所有割邊的一個(gè)端點(diǎn)為 \(s\) 或 \(t\)。因?yàn)槌_與源匯相連的邊，其余邊的容量均為正無(wú)窮，那么最小割是肯定不會(huì)割掉這類邊的。
- 性質(zhì) 2：網(wǎng)絡(luò) \(N\) 的閉合圖與簡(jiǎn)單割一一對(duì)應(yīng)：\(V_1 \cup \{s\} = S\)。
證明從略。
- 性質(zhì) 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\)。
因?yàn)楦?\([S,T]\) 其實(shí)就是源與 \(V_1'\) 的連邊與匯與 \(V_1\) 的連邊，根據(jù)網(wǎng)絡(luò) \(N\) 的構(gòu)造方式可得上式。
- 性質(zhì) 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||
\]
根據(jù)性質(zhì) 4，我們可以通過計(jì)算網(wǎng)絡(luò) \(N\) 的最小割來(lái)計(jì)算最大權(quán)閉合圖的權(quán)值。
2.例題
最大權(quán)閉合圖板子題。
對(duì)于一個(gè)用戶群，他依賴兩個(gè)中轉(zhuǎn)站 \(a_i,b_i\)，開通中轉(zhuǎn)站需要一定成本，這個(gè)成本就是對(duì)我們的負(fù)貢獻(xiàn)，而開通中轉(zhuǎn)站能獲得一些用戶群的收益，這是正貢獻(xiàn)，據(jù)此信息建圖跑最大流即可，不難通過。
#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[N],cur[N],e[N << 1],ne[N << 1],idx;
ll d[N],w[N],ret; bool vis[N];
il void add(int a,int b,ll c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = 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[i] = inff,cur[i] = h[i],vis[i] = 0;
queue<int> q; q.push(s); d[s] = 0;
while (sz(q)) {
int u = q.front(); q.pop();
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (w[i] > 0 && d[j] == inff) {
d[j] = d[u] + 1;
vis[j] = 1; q.push(j);
}
}
}
return d[t] < inff;
}
il ll dfs(int u,ll val) {
if (u == t) return val;
ll now = 0;
for (int i = cur[u]; ~i; i = ne[i]) {
cur[u] = i;
int j = e[i];
if (w[i] > 0 && d[j] == d[u] + 1) {
ll x = dfs(j,min(w[i],val - now));
if (x <= 0) continue;
now += x;
w[i] -= x; w[i ^ 1] += 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;
}
此題不僅需要求出最大權(quán)閉合圖的最大權(quán)，還需要輸出相應(yīng)方案。
根據(jù)性質(zhì) 3，不難發(fā)現(xiàn)網(wǎng)絡(luò)上割掉的邊（滿流的邊）即為 \(V_1\) 中的負(fù)貢獻(xiàn)點(diǎn)向匯的連邊以及 \(V_1\) 補(bǔ)集中正貢獻(xiàn)點(diǎn)向源的連邊。實(shí)際上對(duì)于割 \([S,T]\)，我們的方案就是集合 \(S - \{s\} = V_1\)。
這一點(diǎn)體現(xiàn)在代碼上就是在我們不能再繼續(xù)增廣的時(shí)候最后一遍 bfs 分層參與分層的點(diǎn)即為 \(S\) 集合中的點(diǎn)。所以做完 Dinic 后直接判斷當(dāng)前點(diǎn)是否參與分層就能輸出方案。
這個(gè)題輸入格式比較難受。
#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[N],e[N],ne[N],idx;
ll d[N],w[N];
bool vis[N];
int cur[N];
ll res;
int nail;
string str;
int read(){
if(nail>=str.size())return 0;
int b=0;
while(nail<str.size() and (str[nail]<'0' or str[nail]>'9'))nail++;
while(nail<str.size() and str[nail]>='0' and str[nail]<='9'){
b=b*10+str[nail]-'0';
nail++;
}
return b;
}
il void add(int a,int b,ll c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = 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[i] = 0,d[i] = inff,cur[i] = h[i];
queue<int> q; q.push(s);
vis[s] = 1; d[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (d[u] + 1 < d[j] && w[i]) {
d[j] = d[u] + 1;
if (!vis[j]) {
vis[j] = 1;
q.push(j);
}
}
}
}
if (d[t] == 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[u]; ~i; i = ne[i]) {
cur[u] = i;
int j = e[i];
if (d[j] == d[u] + 1 && w[i]) {
ll x = dfs(j,min(w[i],val - now));
// if (!x) d[j] = -1;
if (x) {
now += x;
w[i] -= x; w[i ^ 1] += 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[i] != inff) printf("%lld ",i); puts("");
rep(i,1,n) if(d[i + m] != 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.練習(xí)題
其實(shí)是個(gè)變式。
要求最小權(quán)閉合圖，所以邊權(quán)取反后做最大權(quán)閉合圖即可。
#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[N];
int h[N],cur[N],e[N << 1],ne[N << 1],idx;
ll d[N],w[N],ret; bool vis[N];
il void add(int a,int b,ll c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = 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[i] = inf,cur[i] = h[i],vis[i] = 0;
queue<int> q; q.push(s); d[s] = 0;
while (sz(q)) {
int u = q.front(); q.pop();
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (w[i] > 0 && d[j] == inf) {
d[j] = d[u] + 1;
vis[j] = 1; q.push(j);
}
}
}
return d[t] != inf;
}
il ll dfs(int u,ll val) {
if (u == t) return val;
ll now = 0;
for (int i = cur[u]; ~i; i = ne[i]) {
cur[u] = i;
int j = e[i];
if (w[i] > 0 && d[j] == d[u] + 1) {
ll x = dfs(j,min(w[i],val - now));
if (x <= 0) continue;
now += x;
w[i] -= x; w[i ^ 1] += 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[i]);
if (a[i] < 0) add_edge(s,i,-a[i]);
else add_edge(i,t,a[i]);
sum += max(a[i],0ll);
}
Dinic();
write(sum - ret,'\n');
return ;
}
il void init() {
return ;
}
signed main() {
// init();
int _ = 1;
// read(_);
while (_ -- ) solve();
return 0;
}
完結(jié)撒花 111。
浙公網(wǎng)安備 33010602011771號(hào)