记录编号	10555	评测结果	AAAAAAAAAA
题目名称	[NOI 2006]最大获利	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	1.024 s
提交时间	2009-06-02 19:28:32	内存使用	6.04 MiB

/* 
 * Problem: NOI2006 profit
 * Author: Guo Jiabao
 * Time: 2009.6.2 18:53
 * State: Unsolved
 * Memo: 网络流 最小割 Dinic
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=55003,MAXM=(50001*3+5001)*2,INF=0x7FFFFFFF;
struct edge
{
	edge *next,*op;
	int t,c;
}*V[MAXN],*P[MAXN],ES[MAXM],*Stae[MAXN];
int N,M,S,T,Ans,EC;
int Lv[MAXN],Stap[MAXN];
inline void addedge(int a,int b,int c)
{
	ES[++EC].next=V[a];
	V[a]=ES+EC; V[a]->t=b; V[a]->c=c;
	ES[++EC].next=V[b];
	V[b]=ES+EC; V[b]->t=a; V[b]->c=0;
	V[a]->op=V[b]; V[b]->op=V[a];
}
void init()
{
	int i,a,b,c;
	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",&c);
		addedge(i+M,T,c);
	}
	for (i=1;i<=M;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		addedge(i,a+M,INF);
		addedge(i,b+M,INF);
		addedge(S,i,c);
		Ans += c;
	}
}
bool level()
{
	int head=0,tail=-1,i,j;
	memset(Lv,0,sizeof(Lv));
	Lv[S]=1;
	Stap[++tail]=S;
	while (head<=tail)
	{
		i=Stap[head++];
		for (edge *e=V[i];e;e=e->next)
		{
			if (e->c && !Lv[j=e->t])
			{
				Lv[j]=Lv[i]+1;
				Stap[++tail]=j;
				if (j==T)
					return true;
			}
		}
	}
	return false;
}
int augment()
{
	int i,j,delta,flow=0,Stop=1;
	for (i=S;i<=T;i++)
		P[i]=V[i];
	Stap[Stop]=S;
	while (Stop)
	{
		i=Stap[Stop];
		if (i!=T)
		{
			for (;P[i];P[i]=P[i]->next)
				if (P[i]->c && Lv[j=P[i]->t] == Lv[i] + 1)
					break;
			if (P[i])
			{
				Stap[++Stop]=j;
				Stae[Stop]=P[i];
			}
			else
			{
				Stop--;
				Lv[i]=0;
			}
		}
		else
		{
			delta=INF;
			for (i=Stop;i>=2;i--)
				if (Stae[i]->c < delta)
					delta = Stae[i]->c;
			flow += delta;
			for (i=Stop;i>=2;i--)
			{
				Stae[i]->c -=delta;
				Stae[i]->op->c +=delta;
				if (Stae[i]->c == 0)
					Stop=i-1;
			}
		}
	}
	return flow;
}
void dinic()
{
	int Maxflow;
	for (Maxflow=0;level();)
		Maxflow += augment();
	Ans -= Maxflow;
}
int main()
{
	init();
	dinic();
	printf("%d\n",Ans);
	return 0;
}