P4174 [NOI2006] 最大获利 题解

sunqihuan · 2025-02-08 22:56:32 · 题解

前言

建议对最大流最小割有一定的了解再来看此题解。

最小割之最大权闭合子图

定义：

闭合子图：从原图里选出来一些点，满足这些点连到的点都在闭合子图里。也就是说闭合子图是一个点的集合，是自洽的。

最大权闭合子图：在所有的闭合子图中，点权和最大的那个闭合子图，称为最大权闭合子图。

转化为流网络，证明

我们可以为原图 G=(V,E) 构造一个流网络 N=(V_N,E_N)，其中 V_N=V+{s,t}，E_N={(s,u),w_u>0}\cup {(u,t),w_u<0} ∪ E。

其中 c(s,u)=w_u,c(u,t)=-w_u,c(u,v)=∞((u,v)\in E)。

在这个问题里，我们定义一种特殊的割：简单割：一个割里的割边只与 s,t 相连，这个割就是一个简单割。

证明：原图里的每一个闭合子图，都能和流网络里的所有简单割一一对应

我们知道，简单割是所有割的一个子集，那么：

证明：最小割是一个简单割

根据最大流最小割定理，我们知道最大流等于最小割。最大流 |f|=\sum_{u\in V_N} f(s,u)，因为 f(s,u)\le c(s,u)，所以所有的 f(s,u) 都是有限的数，而有限个有限的数相加，得到的还是有限的数，所以最大流是有限的，那么最小割就是有限的，最小割是有限的那最小割就不能包含中间那些无穷大的边，所以最小割是一个简单割。

所以我们这里只需要证明闭合子图，都能和流网络里的所有简单割一一对应，那么我们求闭合子图的最值，就可以求简单割的最值对吧。

我们设闭合子图的点集为 V'，我们构造这样一个割 [S,T]：

S=V'+s,T=V_N-S

显然这是一个合法的割。

证明：上述构造的割 [S,T] 是简单割

因为 V' 是一个闭合子图，所以在割 [S,T] 里，能通过中间那些无穷大容量的边走到的点一定也在 V' 里，也就是在 S 里。所以从 S 如果能通过无穷大的边走到 T 里的一个点，那么它走到的那个点一定在 S 里，与在 T 里相矛盾，所以不存在容量为无穷大的割边，所以割 [S,T] 是简单割。

证明：每一个简单割都能和一个闭合子图对应

我们的割 [S,T]，V'=S-s，那 V' 是不是一个闭合点集呢？

因为我们的割 [S,T] 是简单割，所以不存在可以从 S 指向 T 的边是原图里的（就是容量是无穷大的那些边），所以在 S 里走容量原图的边走来走去一定在 S 里，所以 S 就是一个闭合子图，所以每一个简单割都能和一个闭合子图对应。

而我们的割 [S,T] 就是通过闭合子图来定义的，所以结合上述证明，可以得到原图里的每一个闭合子图，都能和流网络里的所有简单割一一对应。

证毕。

然后我们来推导一下割容量 c[S,T] 的表达式。

定义闭合子图为 V_1，V_2=V-V_1，割的容量 c[S,T] 就是 S 到 T 的容量，所以 S=V_1+s,T=V_2+t。所以我们可以分为 4 种情况：

1.V_1 到 V_2 的容量。由于不存在内部的边可以指向 T，所以不存在。

2.V_1 到 t 的容量。

3.s 到 V_2 的容量。

4.s 到 t 的容量。由于 s 不能指向 t，所以不存在。

所以：

我们定义 V_1^+ 表示 V_1 里权值为正数的点的集合， V_1^- 表示 V_1 里权值为负数的点的集合。

设 w(X) 表示 X 里点的权值和，

我们把 w(V_1) 拆开，得：

回顾之前的定义，可以发现，所有从 s 出发的边连到的点点权都是正的，所有连到 t 的点点权都是负的，所以：

观察到 c[S,T] 和 w(V_1) 都有一项 \sum_{v\in V_1^-} (-w_v)，只是符号不同，所以我们让两式相加：

（因为 V_1+V_2=V）

由于 w(V^+) 是定值，所以我们要让 w(V_1) 尽量大，就要让 c[S,T] 尽量小。所以最大权闭合子图的最大权值就是原图所有点权为正数的点的权值和减去最小割。

例题：最大获利

P4174 [NOI2006] 最大获利

我们把中转站和用户群当成点，把公司收入当成点权（当然建中转站要付钱的话就是负数），边就是用户向要求连接的两个中转站分别连接，从源点连向所有用户群（因为收益为正），所有中转站连向汇点，用所有用户群的收益之和减去最小割即可。

不过我们发现这其实是一个大材小用的解法，因为图本来很特殊，一个用户只能连两条边，这种解法相当于是一个用户连多条边的解法。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=55005,M=(50005*3+5000)*2+5,inf=1e8;
int n,m,S,T;
int h[N],e[M],f[M],nt[M],idx;
int q[N],d[N],cur[N];
void add(int a,int b,int c) {
    e[idx]=b;
    f[idx]=c;
    nt[idx]=h[a];
    h[a]=idx++;
    e[idx]=a;
    f[idx]=0;
    nt[idx]=h[b];
    h[b]=idx++;
}
bool bfs() {
    int head=0,tail=0;
    memset(d,-1,sizeof(d));
    q[0]=S,d[S]=0,cur[S]=h[S];
    while(head<=tail) {
        int t=q[head++];
        for(int i=h[t]; ~i; i=nt[i]) {
            int v=e[i];
            if(d[v]==-1 && f[i]) {
                d[v]=d[t]+1;
                cur[v]=h[v];
                if(v==T)return 1;
                q[++tail]=v;
            }
        }
    }
    return 0;
}
int find(int u,int limit) {
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u]; ~i && flow<limit; i=nt[i]) {
        cur[u]=i;
        int v=e[i];
        if(d[v]==d[u]+1 && f[i]) {
            int t=find(v,min(f[i],limit-flow));
            if(!t)d[v]=-1;
            f[i]-=t;
            f[i^1]+=t;
            flow+=t;
        }
    }
    return flow;
}
int dinic() {
    int r=0,flow;
    while(bfs())while(flow=find(S,inf))r+=flow;
    return r;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    S=0,T=n+m+1;
    memset(h,-1,sizeof(h));
    for(int i=1; i<=n; i++) {
        int p;
        cin>>p;
        add(m+i,T,p);
    }
    int tot=0;
    for(int i=1; i<=m; i++) {
        int a,b,c;
        cin>>a>>b>>c;
        add(S,i,c);
        add(i,m+a,inf);
        add(i,m+b,inf);
        tot+=c;
    }
    cout<<tot-dinic()<<endl;
    return 0;
}

最小割之最大密度子图

定义

最大密度子图：是无向图 G=(V,E) 的一个子图，从原图里选一些点和一些边，选的点集为 V'，边集为 E'，满足如果一条边被选了，那么它的两个端点必选。一种选法的密度定义为 \cfrac{|E'|}{|V'|}，密度最大的一种选法称为最大密度子图。

这也很好理解，就是点确定时，边越多，看起来就越密集对吧。

我们发现最大密度子图问题其实可以转化成最大权闭合子图问题。因为有一个条件是选了边 (a,b)，就必须选 a 和 b。所以我们可以直接把点和边都看成点，直接转化成最大获利问题即可。

发掘性质

但是我们直接这么做并没有发掘最大密度子图的性质。所以效率肯定不高。

我们注意到，如果点集确定，那么它的诱导子图一定是最优解，相当于把里面所有的边都选上了。

首先我们看一下密度定义即 \cfrac{|E'|}{|V'|}，看到分数大家应该都会想到分数规划。即设 \cfrac{|E'|}{|V'|}=g，移项得 |E'|-g|V'|。

我们就是要让 |E'|-g|V'| 最大。可惜我们的最小割求的是最小值，所以我们干脆让 g|V'|-|E'| 最小。

我们求这个式子其实不是很好求，我们要尽量和割联系起来。要是把选出来的点集当做割的话，可以用一种补集的思想，就是 S 里面边的数量等于从 S 连出去的边的数量，减去连到 T 的边的数量。

我们给一条边划分一下归属，让一条边 (u,v) 分为两半，一半是靠近 u 的长度为 \frac{1}{2} 的边，另一半是靠近 v 的长度是另一半。即：

所以：

其中 d_v 表示 v 的度数，V'_2 表示 V' 加上其周围的点。

我们构造一张流网络，点就是所有点加上源汇点，边是所有边加上源点到所有点的边和所有点到汇点的边，这里有向无向都没关系。每个点到汇点边的容量为 2g-d_v，由于可能会有负数，所以我们将每条边加上一个大整数偏移量 U，从源点出发的边的容量都是 U，每个点到汇点边的容量为 2g-d_v+U。

设有一割 [S,T]，定义 V'=S-s,V'_2=V-V'，则边像最大权闭合子图一样分为四个情况，只有 s 到 t 是不行的。所以：

c[S,T]\ =\sum_{v\in v'2} U+\sum{u\in V'}(U+2g-\sum{v\in V'} c(u,v))\ =\sum{v\in V} U+\sum{u\in V'} 2g-\sum{u\in V'}\sum_{v\in V'}c(u,v)\ =U\times n+2g|V'|-2|E'|\ =U\times n+2(g|V'|-|E'|)