NOI2006 最大获利洛谷P4174

洛谷题目传送门!

题目描述

新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU 集团旗下的 CS&T 通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。

在前期市场调查和站址勘测之后，公司得到了一共 N 个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第 i个通讯中转站需要的成本为PiP_iP

另外公司调查得出了所有期望中的用户群，一共 M 个。关于第 i 个用户群的信息概括为AiA_iABiB_iBCiC_iCCiC_iCAiA_iABiB_iB

THU 集团的 CS&T 公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 – 投入成本之和）

输入输出格式

输入格式：

输入文件中第一行有两个正整数 N 和 M 。

第二行中有 N 个整数描述每一个通讯中转站的建立成本，依次为P1,P2,…,PNP_1 , P_2 , …,P_NP

以下 M 行，第(i + 2)行的三个数Ai,BiA_i , B_iACiC_iC

所有变量的含义可以参见题目描述。



输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

说明

样例：选择建立 1、2、3 号中转站，则需要投入成本 6，获利为 10，因此得到最大收益 4。

很明显，直接用网络流模板。

首先考虑如何建模型：

先建立超级源点（废话）， 然后连向每一个中转站，流量为成本 cost。 然后再从中转站连向使用它的用户，流量为INF （选择不影响价格，因此流量无限大）。最后从用户流向汇点，
流量为获利gain。
接着，算出所有用户gain的总值，减掉最小割（最大流）即可。

So， Why？

首先先看我们需要计算的是什么： 总获利 - 总成本。
对于亏本用户，其gain 小于 cost， 从其流出的流量肯定 <= gain。因此我们将这部分剪掉，相当于收益为0.
对于赚钱用户，其gain 大于 cost， 从其流出的流量肯定 <= cost。因此我们将这部分剪掉，相当于剪掉了cost，即为实际利润。

因此，建图完成。当前弧优化（不能忘，否则T掉）+ Dicnic 板子。  （当然，用SPFA的最小费用最大流版本也能跑，
设单位费用为1即可，但是速度好像更慢，内存更大）。那为什么还用，雾。

#include <bits/stdc++.h>

using namespace std;

#define N 500010

#define ll long long

#define INF (~0u>>1)

#define isdigit(c) ((c)>='0'&&(c)<='9')

// https://www.luogu.com.cn/problem/P4174

inline int read(){

    ll x = , s = ;

    char c = getchar();

    while(!isdigit(c)){

        if(c == '-')s = -;

        c = getchar();

    }

    while(isdigit(c)){

        x = x *  + c - '';

        c = getchar();

    }

    return x * s;

}

struct node{

    int u, v, w;

    int next = -;

}t[N];

int f[N];

int ht, s;

int deth[N], cur[N];

int n, m;

int bian = -;//全部从-1开始

void addedge(ll u, ll v,ll w){

    bian++;

    t[bian].u = u;

    t[bian].v = v;

    t[bian].w = w;

    t[bian].next = f[u];

    f[u] = bian;

    return ;

}

inline void add(ll u, ll v,ll w){   //注意要加反边。这里就如此写了

    addedge(u, v, w);

    addedge(v, u, );

    return ;

}

queue <int> q;

bool bfs(int s, int ht){

    memset(deth, , sizeof(deth));

    while(!q.empty())q.pop();//进行初始化

    q.push(s);

    deth[s] = ;//起点记得设为-1

    while(!q.empty()){

        int now = q.front();q.pop();

        for(int i = f[now]; ~i; i = t[i].next){

            int v = t[i].v, u = t[i].u, w = t[i].w;

            if(!deth[v] && w > ){

                deth[v] = deth[u] + ; // 分层操作

                q.push(v);

            }

        }

    }

    return deth[ht] != ;

}

ll dfs(int now,int dist){

    if(now == ht)return dist;

    for(int& i = cur[now]; ~i; i = t[i].next){ // 记得当前弧优化

        int w = t[i].w, v = t[i].v, u = t[i].u;

        if(deth[v] == deth[u] +  && w){

            int di = dfs(v, min(dist, w));

            if(di > ){

                t[i].w -= di;

                t[i^].w += di;

                return di;

            }

        }

    }

    return ;

}

ll Dicnic(){ // 经典Dicnic 操作，就是板子

    ll ans = ;

    while(bfs(s, ht)){

        memcpy(cur, f, sizeof(cur));

        while(ll temp = dfs(s,INF))

            ans += temp;

    }

    return ans;

}

int main(){

//    freopen("P4174_9.in", "r", stdin);

    memset(f, -, sizeof(f));

    n = read(), m = read();

    for(int i = ;i <= n; i++){

        int temp = read();

        add(, i, temp); // 从源点连向中转站

    }

    ll ans = ;

    int to1, to2, temp;

    for(int i = ;i <= m; i++){

        int to1 = read(), to2 = read(), temp = read();

        add(to1, i + n, INF);

        add(to2, i + n, INF);

        add(i + n,  + m + n, temp);//从用户连向汇点

        ans += temp;

    }

    s = , ht = n + m + ;

    ans -= Dicnic();//减掉届不到的用户和届到的中转站

    printf("%lld\n", ans);

    return ;

}

典型的脑子题，动手简单动脑难

获利