[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

Sample Output

Solution

考虑最小割模型。

对于每个基站设点(A_i)，对每种人设点(B_i)。
对于每个(A_i)连边(s o A_i)，容量为当前点费用。
对于每个(B_i)，连边(B_i o t)，容量为当前获利。
对于每种约束，连边(A_i o B_j)，容量为(+infty)。

然后这个图的最小割就是最小的损失，答案就是获利总和减去损失。

考虑下为啥是对的，这里其实是用了一个正无穷的边来限制一种约束，也就是说正无穷边两边的边不能同时存在。

#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}

const int maxn = 2e5+10;
const int inf = 1e9;

int n,m,s,t,ans,tot=1;
int head[maxn],vis[maxn],dis[maxn];
struct edge{int to,nxt,w;}e[maxn<<1];

void add(int u,int v,int w) {e[++tot]=(edge){v,head[u],w},head[u]=tot;}
void ins(int u,int v,int w) {add(u,v,w),add(v,u,0);}

int bfs() {
	memset(vis,0,(t+1)*4);
	memset(dis,63,(t+1)*4);
	queue<int > q;q.push(s),vis[s]=1,dis[s]=0;
	while(!q.empty()) {
		int now=q.front();q.pop();
		for(int i=head[now];i;i=e[i].nxt)
			if(e[i].w>0&&!vis[e[i].to]) {
				dis[e[i].to]=dis[now]+1;
				if(e[i].to==t) return 1;
				q.push(e[i].to),vis[e[i].to]=1;
			}
   	}return 0;
}

int dfs(int u,int f) {
	if(u==t) return f;
	int used=0;
	for(int i=head[u];i;i=e[i].nxt)
		if(e[i].w>0&&dis[e[i].to]==dis[u]+1) {
			int d=dfs(e[i].to,min(e[i].w,f-used));
			if(d>0) e[i].w-=d,e[i^1].w+=d,used+=d;
			if(used==f) break;
		}dis[u]=-1;return used;
}

int dinic() {
	int flow=0;
	while(bfs()) flow+=dfs(s,inf);
	return flow;
}

int main() {
	read(n),read(m);s=n+m+2,t=s+1;
	for(int i=1,x;i<=n;i++) read(x),ins(s,i,x);
	for(int i=1,x,y,z;i<=m;i++) {
		read(x),read(y),read(z);
		ins(x,n+i,inf);ins(y,n+i,inf);
		ins(n+i,t,z);ans+=z;
	}
	write(ans-dinic());
	return 0;
}