bzoj1497【NOI2006】最大獲利
Description
新的技術正沖擊著手機通訊市場，對於各大運營商來說，這既是機遇，更是挑戰。THU集團旗下的CS&T通訊公司在新一代通訊技術血戰的前夜，需要做太多的准備工作，僅就站址選擇一項，就需要完成前期市場研究、站址勘測、最優化等項目。在前期市場調查和站址勘測之後，公司得到了一共N個可以作為通訊信號中轉站的地址，而由於這些地址的地理位置差異，在不同的地方建造通訊中轉站需要投入的成本也是不一樣的，所幸在前期調查之後這些都是已知數據：建立第i個通訊中轉站需要的成本為Pi（1≤i≤N）。另外公司調查得出了所有期望中的用戶群，一共M個。關於第i個用戶群的信息概括為Ai, Bi和Ci：這些用戶會使用中轉站Ai和中轉站Bi進行通訊，公司可以獲益Ci。（1≤i≤M, 1≤Ai, Bi≤N） THU集團的CS&T公司可以有選擇的建立一些中轉站（投入成本），為一些用戶提供服務並獲得收益（獲益之和）。那麼如何選擇最終建立的中轉站才能讓公司的淨獲利最大呢？（淨獲利 = 獲益之和 - 投入成本之和）
Input
輸入文件中第一行有兩個正整數N和M 。第二行中有N個整數描述每一個通訊中轉站的建立成本，依次為P1, P2, …, PN 。以下M行，第(i + 2)行的三個數Ai, Bi和Ci描述第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
HINT
【樣例說明】選擇建立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。
Source
網絡流
最小割的應用
先定義s割為選，t割為不選。
我們可以先將所有收益加起來，再減去最小代價，即為最終答案。
從源點s到所有用戶節點i連邊(s,i,c[i])，表示如果用戶i不能滿足，就會付出c[i]的代價。
從所有中轉站節點i到匯點t連邊(i,t,p[i])，表示如果要建立中轉站i，就要付出p[i]的代價。
然後考慮用戶對中轉站的要求，兩個中轉站中只要有一個沒有，這個用戶就不能滿足，即只要有一個中轉站屬於t割，那該用戶也屬於t割。只要連邊(i,a[i],inf)和(i,b[i],inf)，因為長度為inf的邊是一定不會成為割的。這個方法很巧妙。
#include
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define pa pair
#define maxn 60000
#define maxm 320000
#define inf 1000000000
using namespace std;
struct edge_type
{
int next,to,v;
}e[maxm];
int head[maxn],cur[maxn],dis[maxn];
int n,m,s,t,cnt=1,ans=0,x,y,z;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void add_edge(int x,int y,int v)
{
e[++cnt]=(edge_type){head[x],y,v};head[x]=cnt;
e[++cnt]=(edge_type){head[y],x,0};head[y]=cnt;
}
inline bool bfs()
{
queueq;
memset(dis,-1,sizeof(dis));
dis[s]=0;q.push(s);
while(!q.empty())
{
int tmp=q.front();q.pop();
if (tmp==t) return true;
for(int i=head[tmp];i;i=e[i].next) if (e[i].v&&dis[e[i].to]==-1)
{
dis[e[i].to]=dis[tmp]+1;
q.push(e[i].to);
}
}
return false;
}
inline int dfs(int x,int f)
{
int tmp,sum=0;
if (x==t) return f;
for(int &i=cur[x];i;i=e[i].next)
{
int y=e[i].to;
if (e[i].v&&dis[y]==dis[x]+1)
{
tmp=dfs(y,min(f-sum,e[i].v));
e[i].v-=tmp;e[i^1].v+=tmp;sum+=tmp;
if (sum==f) return sum;
}
}
if (!sum) dis[x]=-1;
return sum;
}
inline void dinic()
{
while (bfs())
{
F(i,1,t) cur[i]=head[i];
ans-=dfs(s,inf);
}
}
int main()
{
n=read();m=read();
s=n+m+1;t=s+1;
F(i,1,n)
{
z=read();
add_edge(i+m,t,z);
}
F(i,1,m)
{
x=read();y=read();z=read();
ans+=z;
add_edge(s,i,z);
add_edge(i,x+m,inf);
add_edge(i,y+m,inf);
}
dinic();
printf("%d\n",ans);
}
