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。

相關日誌