最大获利问题

解题思路

有若干个中转站，建立每个中转站都需要花费对应的成本。我们还有若干个用户群，每个用户群连接两个中转站，我们要向满足某个用户群的需求，就必须建立对应的两个中转站，因此我们可以从用户群向对应的两个中转站分别连一条有向边，表示如果想满足这个用户群的需求就必须要两个中转站建立起来。而满足每个用户群的需求都能获得对应的收益。

本题要求最大获利，获利就是总收益减去总成本。可以发现成本都是要减去的，收益都是要增加的。因此如果将所有中转站和用户群看作节点，那么所有中转站的权值就是负的，所有用户群的权值就是正的，选取任何一个用户群，都要算上对应的两个中转站，即从该用户群出发能到的所有点都需要选上，因此在选点的时候其实就是在选闭合点集，而我们的目标是使选的所有点的权值和最大，其实就是让我们求整张图的最大权闭合子图。

因此本题只需要按照求最大权闭合子图的步骤去求即可，首先是建图，从源点向所有正权点连边，容量就是权值；从所有负权点向汇点连边，容量就是权值的绝对值；所有用户群向需要建造的中转站连边，容量是 $+\infty$。然后求一下最小割，最大权值和就是正权点的权值和减去最小割的容量。（具体证明看 最大权闭合图的相关概念 ）

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 55010, M = (100000 + N) * 2 + 10, INF = 0x3f3f3f3f;

int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int q[N], d[N], cur[N]; //队列、层数、当前弧

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

bool bfs() //建立分层图，判断是否存在增广路径
{
    int hh = 0, tt = 0;
    q[0] = S;

    memset(d, 0, sizeof d);
    d[S] = 1;

    cur[S] = h[S];

    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(!d[j] && w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];

                if(j == T) return true;

                q[++tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int flow) //统计从 u 往终点能传输的最大流量，上限是 flow
{
    if(u == T) return flow;

    int rest = flow;
    for(int i = cur[u]; i != -1 && rest; i = ne[i])
    {
        cur[u] = i;

        int j = e[i];
        if(d[j] == d[u] + 1 && w[i])
        {
            int k = find(j, min(w[i], rest));
            if(!k) d[j] = 0;

            w[i] -= k;
            w[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}

int dinic() //求最小割
{
    int maxf = 0, flow;
    while(bfs())
        while(flow = find(S, INF)) maxf += flow;
    return maxf;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h); //初始化邻接表

    //用户群编号：1 ~ m，中转站编号：m + 1 ~ m + n
    S = 0, T = n + m + 1; //源点、汇点
    int sum = 0; //统计正权点的权值和

    //建图
    for(int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        add(m + i, T, x); //从中转站向汇点连一条容量是成本的边
    }
    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(i, m + a, INF), add(i, m + b, INF); //从用户群向需要的中转站连一条容量是 INF 的边
        add(S, i, c); //从源点向用户群连一条容量是收益的边
        sum += c; //记录正权点的权值和
    }

    printf("%d\n", sum - dinic()); //最大权值和 = 正权点的权值和 - 最小割

    return 0;
}