记录编号	190650	评测结果	AAAAAAAAAA
题目名称	[NOI 2006]最大获利	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.150 s
提交时间	2015-10-03 22:55:47	内存使用	7.18 MiB

#include<cstdio>
#include<deque>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int SIZEN=5010,SIZEM=50010,maxn=0x7fffffff/2;
int N,M,tot=0,S=0,T;
int P[SIZEN],d[SIZEN]={0};
int H[SIZEN];
LL e[SIZEN],U=0;
deque<int> Q;
vector<int> s[SIZEN];
class miku
{
public:
	int fr,to,cap,flow;
	miku(){}
	miku(int a,int b,int c,int d)
	{
		fr=a,to=b,cap=c,flow=d;
	}
}E[8*(SIZEN+SIZEM)];
void add(int fr,int to,int cap)
{
	s[fr].push_back(tot);
	E[tot++]=miku(fr,to,cap,0);
	s[to].push_back(tot);
	E[tot++]=miku(to,fr,0,0);
}
void read()
{
	scanf("%d%d",&N,&M);
	T=N+1;
	for(int i=1;i<=N;i++) 
	{
		scanf("%d",&P[i]);
		U+=P[i];
	}
	U*=2;
	int a,b,c;
	for(int i=1;i<=M;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		d[a]+=c;d[b]+=c;
		add(a,b,c);add(b,a,c);
		U+=c;
	}
	for(int i=1;i<=N;i++)
	{
		add(0,i,U);add(i,T,U+2*P[i]-d[i]);
	}
}
int min(int a,LL b)
{
	if(b<a) return b;
	else return a;
}
void push(int x,int t)
{
	miku &v=E[t];
	int flow=min(v.cap-v.flow,e[x]);
	e[x]-=flow,v.flow+=flow,e[v.to]+=flow,E[t^1].flow-=flow;
	if(v.to!=S&&v.to!=T&&e[v.to]>0) Q.push_back(v.to);
}
void use_up(int x)
{
	int mi;
	while(e[x])
	{
		mi=maxn;
		for(int i=0;i<s[x].size();i++)
		{
			miku &v=E[s[x][i]];
			if(v.cap<=v.flow) continue;
			if(H[v.to]==H[x]-1)
			{
				push(x,s[x][i]);
				if(!e[x]) break;
			}
			else if(H[v.to]<mi) mi=H[v.to];
		}
		if(!e[x]) break;
		H[x]=mi+1;
	}
}
LL maxflow()
{
	memset(H,0,sizeof(H));
	memset(e,0,sizeof(e));
	H[0]=N;if(H[0]>10) H[0]=10;
	e[0]=U*N;
	for(int i=0;i<s[0].size();i++) push(0,s[0][i]);
	while(!Q.empty())
	{
		int x=Q.front();Q.pop_front();
		use_up(x);
	}
	return e[T];
}
void work()
{
	//cout<<U<<endl;
	LL ans=(N*U-maxflow())/2;
	printf("%lld",ans);
}
int main()
{
	freopen("profit.in","r",stdin);
	freopen("profit.out","w",stdout);
	read();
	work();
	return 0;
}