首页 > 其他分享 >最大权闭合图

最大权闭合图

时间：2025-01-05 19:55:14浏览次数：3  
标签：ch return 最大 int ptc 闭合 il define

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)\)：

  1. 建立源点 \(s\) 与汇点 \(t\)；
  2. 对于原图中的边 \((u,v)\)，建立容量为 \(+\infty\) 的有向边；
  3. 对于原图中的点 \(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\)。
因为割 \([S,T]\) 其实就是源与 \(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[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;
}

II.P2762 太空飞行计划问题

此题不仅需要求出最大权闭合图的最大权，还需要输出相应方案。
根据性质 3，不难发现网络上割掉的边（满流的边）即为 \(V_1\) 中的负贡献点向汇的连边以及 \(V_1\) 补集中正贡献点向源的连边。实际上对于割 \([S,T]\)，我们的方案就是集合 \(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[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.练习题

其实是个变式。

III.AT_arc085_c MUL

因为删除一个数其相应的倍数也会被删除，依赖关系是可能是从负贡献到正贡献，故我们考虑将负贡献点向源连边，正贡献点向汇连边，然后跑 Dinic，最后答案依然是正贡献点权之和减去最小割。

#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;
}

完结撒花 111。

标签：ch,return,最大,int,ptc,闭合,il,define
From： https://www.cnblogs.com/songszh/p/18651840/Maximum-Weight-Closure-of-a-Graph

相关文章

  • 整数序列的元素最大跨度值题解
    【题目要求】求出n个数中的最大跨度值（最大值-最小值）。一、求出最大值如果a比最大值（max）还要大，那么最大值（max）就变成a，最后max就是n个数中最大的数。二、求出最小值如果a比最小值（min）还要小，那么最小值（min）就变成a，最后min就是n个数中最小的数。【题解代码】#include<bits/stdc++.h>usin......
  • 整数序列的元素最大跨度值
    (题目要求)此题是需要求出n个数中最大跨度值,最小跨度值(最大跨度值=最大值减去最小值)1.先求出最大值如果a比最大值max还大，那么最大值等于a。2.再求出最小值如果a比最小值min还小，那么最小值等于a。#include<bits/stdc++.h>usingnamespacestd;intmain(){ intn,a,max=0,min=......
  • 接受一个字符串作为参数，并返回该字符串中出现次数最多的字符及其出现次数。如果有多个
    你可以使用JavaScript来实现这个功能。下面是一个函数，它接受一个字符串作为参数，并返回出现次数最多的字符及其出现次数。如果有多个字符出现次数相同且都是最大次数，则返回其中字母序最小的字符。functionfindMostFrequentChar(str){//创建一个对象来存储字符及其出现次数......
  • 124.二叉树中的最大路径和
    /***@param{TreeNode}root*@return{number}*///子树的最大路径和=左子树提供的最大路径和+根节点值+右子树的的最大路径和，//分别递归遍历左子树和右子树的最大路径和，两者之前取一个最大值；返回；//最后里面，要注意最后得出的是一个负数，直接返回0；否则正常的数据......
  • 2025-01-04：不包含相邻元素的子序列的最大和。用go语言，给定一个整数数组 nums 和一个由
    2025-01-04：不包含相邻元素的子序列的最大和。用go语言，给定一个整数数组nums和一个由二维数组queries组成的查询列表，其中每个查询的格式为queries[i]=[posi,xi]。对于每个查询i，首先将nums[posi]的值更新为xi，然后计算在这一更新后，数组nums中所有不包含相邻元素的子序......
  • 分披萨，关键在于吃货可能取左或者取右，利用max(递归调用左边，递归调用右边），相当于暴力获取
    #include<bits/stdc++.h>usingnamespacestd;intn;//披萨个数intpizza[500];//n个披萨大小longcache[500][500];intcheck(intid){  if(id<0)    id=n-1;//若取走披萨第一块的左边，则循环相当于最后一块  if(id>=n)  {    id=0;//......
  • #C02L02P01. C02.L02.一维数组最值问题.知识点1.求最大值
    从键盘读入n（1<=n<=100）个正整数，输出最大值。算法分析假设一个最大值maxx=0；maxx依次跟数组中的元素进行比较；如果该数组元素大于maxx，则将该数组元素值赋值给maxx；maxx即为该数组中的最大值。参考代码#include<bits/stdc++.h>usingnamespacestd;intn,x[101......
  • 数组中的第k个最大元素(快速排序)
    给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例1:输入:[3,2,1,5,6,4],k=2输出:5示例 2:输入:[3......
  • 柱状图中最大的矩形(单调递增栈)
    给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为1。求在该柱状图中，能够勾勒出来的矩形的最大面积。示例1:输入：heights=[2,1,5,6,2,3]输出：10解释：最大的矩形为图中红色区域，面积为10示例2：输入：heights=[2,4]输出：4代码思想：进栈......
  • leetcode热题100（84. 柱状图中最大的矩形）c++
    链接：84.柱状图中最大的矩形-力扣（LeetCode）给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为1。求在该柱状图中，能够勾勒出来的矩形的最大面积。示例1:输入：heights=[2,1,5,6,2,3]输出：10解释：最大的矩形为图中红色区域，面积为10示......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99