洛谷P4174-最大获利(最大权闭合子图)

题目链接:洛谷P4174-最大获利

题意:

某公司有n个基站,建立每个基站的花费为P[i],然后该公司有m个用户,每个用户会使用基站A[i]和B[i],然后该公司会获利C[i],问最大获利。

题解:

最大权闭合子图。

把用户和基站都当做点,然后由用户向基站连边,表示该用户要使用的基站,容量为inf,然后由源点向用户连边,容量为C[i],然后基站向汇点连边,容量为P[i],求最小割即可。

参考代码:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5.5e4 + 10;
const int MAXM = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int n, m;
struct EDGE
{
    int v, nxt, w;
} edge[MAXM << 1];
int fir[MAXN], ecnt = 0;
void addedge(int u, int v, int w)
{
    edge[ecnt].v = v, edge[ecnt].w = w, edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
    swap(u, v);
    edge[ecnt].v = v, edge[ecnt].w = 0, edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
}
int cur[MAXN], depth[MAXN];
int dfs(int u, int flow, int st, int ed)
{
    if (u == ed)
        return flow;
    for (int &i = cur[u]; i != -1; i = edge[i].nxt)
    {
        int v = edge[i].v, w = edge[i].w;
        if (depth[v] == depth[u] + 1 && w)
        {
            int di = dfs(v, min(w, flow), st, ed);
            if (di)
            {
                edge[i].w -= di;
                edge[i ^ 1].w += di;
                return di;
            }
        }
    }
    return 0;
}
bool bfs(int st, int ed)
{
    queue<int> q;
    while (!q.empty())
        q.pop();
    memset(depth, 0, sizeof(depth));
    depth[st] = 1;
    q.push(st);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = fir[u]; i != -1; i = edge[i].nxt)
        {
            int v = edge[i].v;
            int w = edge[i].w;
            if (depth[v] == 0 && w)
            {
                depth[v] = depth[u] + 1;
                q.push(v);
            }
        }
    }
    return depth[ed] > 0;
}
int dinic(int st, int ed)
{
    int tot = 0;
    while (bfs(st, ed))
    {
        for (int i = 0; i <= n + m + 1; i++)
            cur[i] = fir[i];
        while (int temp = dfs(st, inf, st, ed))
            tot += temp;
    }
    return tot;
}
int main()
{
    scanf("%d%d", &n, &m);
    ecnt = 0;
    memset(fir, -1, sizeof(fir));
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        addedge(m + i, m + n + 1, x);
    }
    int ans = 0;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        ans += c;
        addedge(0, i, c);
        addedge(i, m + a, inf);
        addedge(i, m + b, inf);
    }
    printf("%d\n", ans - dinic(0, n + m + 1));
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。