记录编号	251259	评测结果	AAAAAAAAAA
题目名称	[NOI 2006]最大获利	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.554 s
提交时间	2016-04-17 14:51:05	内存使用	12.02 MiB

#include<cstdio>
#include<algorithm>
//#include"debug.h"
using namespace std;

const int maxl=99999999;
int n,m,ans,s,t,cnt,p[5010],a[50010],b[50010],c[50010],i,j;
int head[60010],tail[60010],next[500010];
//1..n表示中转站，n+1..n+m表示用户群 
struct edge{
	int f,t,g,oppo;//oppo表示反向边地址 
}w[500010];
void add(int f,int t,int g){
	cnt++;w[cnt].f=f;w[cnt].t=t;w[cnt].g=g;w[cnt].oppo=cnt+1;
	if (head[f]==0) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
	cnt++;w[cnt].f=t;w[cnt].t=f;w[cnt].oppo=cnt-1;
	if (head[t]==0) head[t]=tail[t]=cnt;
		else tail[t]=next[tail[t]]=cnt;
}

int dui[60010],r,l[60010],top;
void bfs(){
	int i,j;
	dui[r=1]=s;l[s]=1;
	for (i=1;i<=t;i++) l[i]=-1;
	for (i=1;i<=r;i++){
		for (j=head[dui[i]];j!=0;j=next[j])
		if (w[j].g>0&&l[w[j].t]==-1){
			dui[++r]=w[j].t;l[w[j].t]=l[dui[i]]+1;
		}	
	}
}
struct stack{
	int x,i,df;
}z[60010];
void change(){
	int i,j=t,r,df=z[top].df;
	ans-=df;
	for (i=top-1;i>0;i--){
		w[z[i].i].g-=df;
		w[w[z[i].i].oppo].g+=df;
		z[i].df-=df;
		if (z[i].df==0) top=i;
	}
}
bool dinic(){
	bfs();
	if (l[t]==-1) return false;
	top=1;z[1].x=s;z[1].i=head[s];z[1].df=maxl;
	while (top>0){
		if (z[top].x==t){
			change();top--;z[top].i=next[z[top].i];continue;
		}
		if (z[top].i==0){
			l[z[top].x]=-1;top--;z[top].i=next[z[top].i];continue;
		}
		if (w[z[top].i].g>0&&l[w[z[top].i].t]==l[z[top].x]+1){
			z[top+1].x=w[z[top].i].t;
			z[top+1].df=min(z[top].df,w[z[top].i].g);
			top++;
			z[top].i=head[z[top].x];
			continue;
		}
		z[top].i=next[z[top].i];
	}
	return true;
}

int main()
{
	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",&p[i]);
		add(i,t,p[i]);
	}
	for (i=1;i<=m;i++){
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
		ans+=c[i];
		add(s,n+i,c[i]);
		add(n+i,a[i],maxl);
		add(n+i,b[i],maxl);
	}
	/*for (i=s;i<=t;i++){
		writel(i);
		for (j=head[i];j!=0;j=next[j]) write(w[j].t);
		writeln;
	}*/
	while (dinic());
	printf("%d\n",ans);
	return 0;
}