记录编号	241282	评测结果	AAAAAAAAAA
题目名称	[NOI 2006]最大获利	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.140 s
提交时间	2016-03-24 22:09:50	内存使用	8.44 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int INF=1000000000;
const int maxn=55010;
const int maxm=600010;
int cnt=1,fir[maxn],nxt[maxm],to[maxm],cap[maxm];
void addedge(int a,int b,int v){
	nxt[++cnt]=fir[a];to[cnt]=b;fir[a]=cnt;cap[cnt]=v;
}

int q[maxn],dis[maxn],gap[maxn],path[maxn],n,m;

void BFS(int S,int T){
	int front=1,back=1;
	memset(dis,0,sizeof(dis));
	dis[T]=1;q[back++]=T;
	while(front<back){
		int node=q[front++];
		for(int i=fir[node];i;i=nxt[i]){
			if(dis[to[i]])continue;
			dis[to[i]]=dis[node]+1;
			q[back++]=to[i];
		}
	}
}
int fron[maxn];
int Max_flow(int S,int T){
	BFS(S,T);
	memset(gap,0,sizeof(gap));
	for(int i=S;i<=T;i++)++gap[dis[i]];
	int ret=0,p=S,f;
	memcpy(fron,fir,sizeof(fir));
	while(dis[S]<=T){
		//printf("%d\n",p);
		if(p==T){
			f=100000000;
			while(p!=S){
				f=min(f,cap[path[p]]);
				p=to[path[p]^1];
			}
			ret+=f;p=T;
			while(p!=S){
				cap[path[p]]-=f;
				cap[path[p]^1]+=f;
				p=to[path[p]^1];
			}
		}
		int &ii=fron[p];
		for(;ii;ii=nxt[ii])
			if(cap[ii]&&dis[p]==dis[to[ii]]+1)
				break;
		
		if(ii)
			path[p=to[ii]]=ii;
		else{
			if(--gap[dis[p]]==0)break;
			int minn=T+1;
			for(int i=fir[p];i;i=nxt[i])
				if(cap[i])
					minn=min(minn,dis[to[i]]);
			gap[dis[p]=minn+1]++;
			ii=fir[p];
			if(p!=S)
				p=to[path[p]^1];
		}		
	}
	return ret;
}

int main(){
	freopen("profit.in","r",stdin);
	freopen("profit.out","w",stdout);
	int ans=0,tot=0;
	scanf("%d%d",&n,&m);
	for(int i=1,d;i<=n;i++){
		scanf("%d",&d);ans-=d;
		tot+=d;
		addedge(0,i,d);
		addedge(i,0,0);
	}
	for(int i=n+1,d,a,b;i<=m+n;i++){
		scanf("%d%d%d",&a,&b,&d);
		tot+=d;
		addedge(a,i,INF);
		addedge(i,a,0);
		
		addedge(b,i,INF);
		addedge(i,b,0);
		
		addedge(i,n+m+1,d);
		addedge(n+m+1,i,0);
	}
	printf("%d\n",ans+tot-Max_flow(0,n+m+1));
}