记录编号	412108	评测结果	AAAAAAAAAA
题目名称	[NOI 2006]最大获利	最终得分	100
用户昵称	xyz117	是否通过	通过
代码语言	C++	运行时间	0.079 s
提交时间	2017-06-07 20:24:43	内存使用	0.90 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF=0x7ffffff;
const int maxm=310001;
const int maxn=56001;
struct node
{
	int v,f,nex;
}edge[maxm];
int head[maxn];
int q[maxn],ans,sum;
int le[maxn],tot=-1,n,m;
void add(int u,int v,int f)
{
	edge[++tot]=(node){v,f,head[u]};
	head[u]=tot;
	edge[++tot]=(node){u,0,head[v]};
	head[v]=tot;
}
bool bfs(int s,int t)
{
	memset(le,0,sizeof(le));
	le[s]=1;
	int fr=0,ta=1,x,i,v,f;
	q[fr]=s;
	while(fr<ta)
	{
		x=q[fr++];
		if(x==t)
			return true;
		for(i=head[x];i!=-1;i=edge[i].nex)
		{
			v=edge[i].v;
			f=edge[i].f;
			if(!le[v]&&f)
			{
				le[v]=le[x]+1;
				q[ta++]=v;
			}
		}
	}
	return false;
}
int dfs(int u,int maxf,int t)
{
	if(u==t)
		return maxf;
	int M,ret=0,v,f,i;
	for(i=head[u];i!=-1;i=edge[i].nex)
	{
		v=edge[i].v;
		f=edge[i].f;
		if(le[u]+1==le[v]&&f)
		{
			M=min(maxf-ret,f);
			f=dfs(v,M,t);
			edge[i].f-=f;
			edge[i^1].f+=f;
			ret+=f;
			if(ret==maxf)
				return ret;
		}
	}
	return ret;
}
int dinic(int s,int t)
{
	ans=0;
	while(bfs(s,t))
		ans+=dfs(s,INF,t);
	printf("%d",sum-ans);
}
int haha()
{
	freopen("profit.in","r",stdin);
	freopen("profit.out","w",stdout);
	int x,y,z;
	scanf("%d%d",&n,&m);
	memset(head,-1,sizeof(head));
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		add(0,i,x);
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		
		add(x,n+i,INF);
		add(y,n+i,INF);
		add(n+i,n+m+1,z);
		sum+=z;
	}
	dinic(0,n+m+1);
	return 0;
}
int sb=haha();
int main()
{;}