Beyond the Void
BYVoid
NOI 2006 最大獲利
本文正體字版由OpenCC轉換

把每個用戶和每個站點都看成一個頂點。建立網絡,從源點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。


上次修改時間 2017-02-03

相關日誌