NOI 2006 最大获利

把每个用户和每个站点都看成一个顶点。建立网络，从源点S向每个用户连接一条容量为收益的有向边，每个用户向相关的两个站点连接一条容量为无穷大的 有向边，每个站点向汇点T连接一条容量为成本的有向边。求出网络最小割集的容量就是Maxflow=（未被选的用户的收益之和 + 被选择的站点的成本之和）。设Total为所有用户的收益之和，我们要求的是（被选的用户的收益之和 - 被选择的站点的成本之和），恰好等于Total - Maxflow，就是最大收益。

为什么是这样的？因为任何一个可行割集对应了一个满足条件的方案，具体来说被选择的顶点就是S集合中的顶点，而割集对应了cut=（未被 选的用户的收益之和 + 被选择的站点的成本之和），我们为了要求的（被选的用户的收益之和 - 被选择的站点的成本之和）= Total - cut尽量大，Total一定，所以要让cut尽量小，直至最小割集。

Dinic秒掉。

/* 
 * Problem: NOI2006 profit
 * Author: Guo Jiabao
 * Time: 2009.6.2 18:53
 * State: Solved
 * Memo: 网络流 最小割 Dinic
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=55003,MAXM=(50001*3+5001)*2,INF=200;
struct edge
{
    edge *next,*op;
    int t,c;
}*V[MAXN],*P[MAXN],ES[MAXM],*Stae[MAXN];
int N,M,S,T,Ans,EC;
int Lv[MAXN],Stap[MAXN];
inline void addedge(int a,int b,int c)
{
    ES[++EC].next=V[a];
    V[a]=ES+EC; V[a]->t=b; V[a]->c=c;
    ES[++EC].next=V[b];
    V[b]=ES+EC; V[b]->t=a; V[b]->c=0;
    V[a]->op=V[b]; V[b]->op=V[a];
}
void init()
{
    int i,a,b,c;
    freopen("profit.in","r",stdin);
    freopen("profit.out","w",stdout);
    scanf("%d%d",&N,&M);
    S=0; T=N+M+1;
    for (i=1;i<=N;i++)
    {
        scanf("%d",&c);
        addedge(i+M,T,c);
    }
    for (i=1;i<=M;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        addedge(i,a+M,INF);
        addedge(i,b+M,INF);
        addedge(S,i,c);
        Ans += c;
    }
}
bool level()
{
    int head=0,tail=-1,i,j;
    memset(Lv,0,sizeof(Lv));
    Lv[S]=1;
    Stap[++tail]=S;
    while (head<=tail)
    {
        i=Stap[head++];
        for (edge *e=V[i];e;e=e->next)
        {
            if (e->c && !Lv[j=e->t])
            {
                Lv[j]=Lv[i]+1;
                Stap[++tail]=j;
                if (j==T)
                    return true;
            }
        }
    }
    return false;
}
int augment()
{
    int i,j,delta,flow=0,Stop=1;
    for (i=S;i<=T;i++)
        P[i]=V[i];
    Stap[Stop]=S;
    while (Stop)
    {
        i=Stap[Stop];
        if (i!=T)
        {
            for (;P[i];P[i]=P[i]->next)
                if (P[i]->c && Lv[j=P[i]->t] == Lv[i] + 1)
                    break;
            if (P[i])
            {
                Stap[++Stop]=j;
                Stae[Stop]=P[i];
            }
            else
            {
                Stop--;
                Lv[i]=0;
            }
        }
        else
        {
            delta=INF;
            for (i=Stop;i>=2;i--)
                if (Stae[i]->c < delta)
                    delta = Stae[i]->c;
            flow += delta;
            for (i=Stop;i>=2;i--)
            {
                Stae[i]->c -=delta;
                Stae[i]->op->c +=delta;
                if (Stae[i]->c == 0)
                    Stop=i-1;
            }
        }
    }
    return flow;
}
void dinic()
{
    int Maxflow;
    for (Maxflow=0;level();)
        Maxflow += augment();
    Ans -= Maxflow;
}
int main()
{
    init();
    dinic();
    printf("%dn",Ans);
    return 0;
}

<h2><span class="mw-headline">最大获利 </span></h2>

【问题描述】

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

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

另外公司调查得出了所有期望中的用户群，一共M 个。关于第i 个用户群的信息概括为Ai, Bi 和Ci：这些用户会使用中转站Ai 和中转站Bi 进行通讯，公司可以获益Ci。（1≤i≤M, 1≤Ai, Bi≤N） THU 集团的CS&amp;T 公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 – 投入成本之和）

【输入文件】
  • 输入文件中第一行有两个正整数N 和M 。
  • 第二行中有N 个整数描述每一个通讯中转站的建立成本，依次为P1, P2, …, PN 。
  • 以下M 行，第(i + 2)行的三个数Ai, Bi 和Ci 描述第i 个用户群的信息。

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

    【输出文件】

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

    【样例输入】 

    5 5
  1 2 3 4 5
  1 2 3
  2 3 4
  1 3 3
  1 4 2
  4 5 3
    【样例输出】 
    4
    【样例说明】

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

    【评分方法】

    本题没有部分分，你的程序的输出只有和我们的答案完全一致才能获得满分，否则不得分。

    【数据规模和约定】

  • 80%的数据中：N≤200，M≤1 000。

  • 100%的数据中：N≤5 000，M≤50 000，0≤Ci≤100，0≤Pi≤100。

相关日志