bzoj - 1497

Posted by WildCow on April 28, 2018

[NOI2006]最大获利

Time Limit: 5000ms
Memory Limit: 64mb

Description

新的技术正冲击着手机通讯市场,对于各大运营商来说,这既是机遇,更是挑战。THU集团旗下的CS&T通讯公司在新一代通讯技术血战的前夜,需要做太多的准备工作,仅就站址选择一项,就需要完成前期市场研究、站址勘测、最优化等项目。在前期市场调查和站址勘测之后,公司得到了一共N个可以作为通讯信号中转站的地址,而由于这些地址的地理位置差异,在不同的地方建造通讯中转站需要投入的成本也是不一样的,所幸在前期调查之后这些都是已知数据:建立第 i 个通讯中转站需要的成本为Pi($1\leqslant i\leqslant N$)。另外公司调查得出了所有期望中的用户群,一共 M 个。关于第 i 个用户群的信息概括为 $A_i,B_i$ 和 $C_i$:这些用户会使用中转站Ai和中转站 $B_i$ 进行通讯,公司可以获益$C_i$。($1\leqslant i\leqslant M,1\leqslant A_i,B_i\leqslant N,$) THU集团的CS&T公司可以有选择的建立一些中转站(投入成本),为一些用户提供服务并获得收益(获益之和)。那么如何选择最终建立的中转站才能让公司的净获利最大呢?(净获利 = 获益之和 - 投入成本之和)

Input

输入文件中第一行有两个正整数N和M 。第二行中有N个整数描述每一个通讯中转站的建立成本,依次为 $P_1,P_2,\cdots ,P_n$ 。以下 M 行,第 (i + 2) 行的三个数 $A_i,B_i$ 和 $C_i$ 描述第 i 个用户群的信息。所有变量的含义可以参见题目描述。

Output

你的程序只要向输出文件输出一个整数,表示公司可以得到的最大净获利。

Sample Input

5 5
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3

Sample Output

4


第一道建好图后没有跑出样例最后还 WA 飞了的网络流
虽然是自己傻逼数组开小了
不过这题还是蛮有意思的

先按照题意,我们建一个图
第 i 个站用顶点 i 表示,权值为 $-P_i$
对于使用站 $A_j$ 和 $B_j$ 的用户 j
我们用一条权值为 $C_j$ 的边连接 $A_j, B_j$

然后我们的目标是没有蛀牙寻找一个点集
使这个点集以及连接这个点集中的点的所有边的权值和最大

于是我们可以将每条边的权值分配到其连接的节点上,使其权值变成 0
这样一来边权剩下的值就是我们的收益
所以我们的目标是让每条边尽可能多的分配权值到其连接的节点上
同时权值变成 0 的节点应该尽可能多

假设我们已经达成了这个成就
我们会发现分配完后存在有的节点的权值依然是负的
这就说明我们现在在亏损
所以我们考虑把这些负权的点,连带着连着这些点的给劝退
然后考虑用户对中转站的要求,两个中转站中只要有一个没有,这个用户就不能满足,即我们要把那些和负权连接的边也给劝退

这样一来又会有一些节点变成负的,因为原先对这些点有贡献的边被劝退了
同时与这些新增的负权节点相连的边的边权一定为 0

因为新增的负权节点 $V_0’$通过之前被劝退的一条边 $E_0$ 与之前被劝退的节点 $V_0 $相连
如果在初次分配后存在另一条边权不为 0 的边 $E_0’$ 与 $V_0’$ 相连
那么我们可以把 $E_0’$ 的值通过 $V_0’ -> E_0 -> V_0$ 转移到 $V_0$ 上
构成新的匹配

然后我们不断删除新增的负权节点及与他相连的边

这样一来我们有最大净收益:
$\sum{C_i}-\sum{P_i}+$所有删除的节点建造成本-所有删除的边的初始收益
= $\sum{C_i}$ - 所有剩余节点的成本 - 所有删除边的初始收益

这样一来问题转化成如何实现两个尽可能多

我们来看看最小割
定义 S 割为选
t 割为不选

源点到所有用户连边 $(ss, i, C_i)$ 如果割在这类边上
表示用户 i 不被满足,获得 $C_i$ 的代价

站到汇点连边 $(j, tt, P_i)$ 如果割在这类边上
表示站 j 被建立,付出 $P_i$ 的代价

然后考虑用户对中转站的要求
两个中转站中只要有一个没有,这个用户就不能满足
即只要有一个中转站属于 t 割,那该用户也属于 t 割
所以我们连边 $(i, a_i, INF),(i, b_i, INF)$ 因为长度为 INF 的边是一定不会成为割的

我们就很容易发现这个图的最小割:所有剩余顶点的成本 + 所有删除边的初始收益
所以有答案:$\sum{C_i} - maxflow$

最后需要注意一下数组大小


#include <bits/stdc++.h>
using namespace std;

const int N = 60050;
const int INF = 0x3f3f3f3f;

struct Node
{
    int to;
    int w;
    int ne;
};

Node node[420000];
int head[N];
int cur[N];
int di[N];
int ma[N];
int top;
int ss, tt;
int a, b;
int n, m;

void add_edge(int from, int to, int w)
{
    node[top].to = to;
    node[top].w = w;
    node[top].ne = head[from];
    head[from] = top;
    top ++;
}

void ini()
{
    top = 0;
    memset(head, -1, sizeof(head));
}

bool build()
{
    queue Q;
    int now;

    memset(di, 0, sizeof(di));
    di[ss] = 1;
    Q.push(ss);
    while(!Q.empty()){
        now = Q.front();
        Q.pop();
        if(now == tt){
            return true;
        }
        for(int i = head[now]; i != -1; i = node[i].ne){
            int v, w;

            v = node[i].to;
            w = node[i].w;
            if(w && !di[v]){
                di[v] = di[now] + 1;
                Q.push(v);
            }
        }
    }

    return false;
}

int dfs(int u, int maxf)
{
    int ans;

    if(u == tt){
        return maxf;
    }
    ans = 0;
    for(int &i = cur[u]; i != -1; i = node[i].ne){
        int v, w;

        v = node[i].to;
        w = node[i].w;
        if(w && di[v] == di[u] + 1){
            int t;

            t = dfs(v, min(maxf - ans, w));
            node[i].w -= t;
            node[i ^ 1].w += t;
            ans += t;
            if(ans == maxf){
                return ans;
            }
        }
    }

    return ans;
}

int Dinic()
{
    int ans;

    ans = 0;
    while(build()){
        for(int i = 1; i <= tt; i ++){
            cur[i] = head[i];
        }
        ans += dfs(ss, INF);
        //printf("ans = %d\n", ans);
    }

    return ans;
}

int main(int argc, char const *argv[])
{
    int t;

    while(scanf("%d%d", &a, &b) == 2){
        ini();
        t = 0;
        n = a + b;
        ss = n + 1;
        tt = n + 2;
        for(int i = 1; i <= a; i ++){
            scanf("%d", &ma[i]);
            add_edge(i, tt, ma[i]);
            add_edge(tt, i, 0);
        }
        for(int i = a + 1; i <= n; i ++){
            int u, v, w;

            scanf("%d%d%d", &u, &v, &w);
            t += w;
            add_edge(ss, i, w);
            add_edge(i, ss, 0);
            add_edge(i, u, INF);
            add_edge(u, i, 0);
            add_edge(i, v, INF);
            add_edge(v, i, 0);
        }
        printf("%d\n", t - Dinic());
    }

    return 0;
}