记录编号	540550	评测结果	AAAAAAAAAA
题目名称	[NOI 2008]志愿者招募	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.131 s
提交时间	2019-08-25 18:16:33	内存使用	18.72 MiB

#include<bits/stdc++.h>
#define I inline 
using namespace std;

const int N=1e5+7;
const int INF=0x3f3f3f3f; 

int cnt=1,m,n,k,maxflow,mincost,cost,s,t; 
int head[N],dis[N],fw[N],pre[N],a[N];
bool inque[N];

struct edge
{
	int nx,to,dist,flow; 
}e[N<<1];

I int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void add_edge(int a,int b,int flow,int dist)
{
	cnt++;e[cnt].to=b;e[cnt].dist=dist;e[cnt].flow=flow;e[cnt].nx=head[a];head[a]=cnt;
	cnt++;e[cnt].to=a;e[cnt].dist=-dist;e[cnt].flow=0;e[cnt].nx=head[b];head[b]=cnt;
}
bool SPFA(int s,int t)
{
	queue<int> que;
	memset(dis,INF,sizeof(dis));memset(inque,0,sizeof(inque));
	dis[s]=0;fw[s]=INF;que.push(s);inque[s]=true;
	while (!que.empty())
	{
		int x=que.front();inque[x]=false;
		for (int i=head[x];i;i=e[i].nx)
		{
			int y=e[i].to;
			if (dis[y]>dis[x]+e[i].dist&&e[i].flow)
			{
				dis[y]=dis[x]+e[i].dist;
				pre[y]=i;
				fw[y]=min(fw[x],e[i].flow);
			    if (!inque[y]) {inque[y]=true;que.push(y);}
			}
		}
		que.pop();
	}
	if (dis[t]==INF) return false;
	else return true;
}
void MCMF(int s,int t)
{
	while (SPFA(s,t))
	{
		int x=t;
		maxflow+=fw[t];
		mincost+=dis[t]*fw[t];
		while (x!=s)
		{
			int i=pre[x];
			e[i].flow-=fw[t];
			e[i^1].flow+=fw[t];
			x=e[i^1].to;
		}
	}
}
int main()
{
	freopen("employee.in","r",stdin);
	freopen("employee.out","w",stdout); 
	n=read(),m=read();s=N-2;t=N-3;
	for (int i=1;i<=n;i++)
	{
		int x=read();add_edge(i,i+1,INF-x,0); 
	}
	for (int i=1;i<=m;i++)
	{
		int x=read(),y=read(),z=read();
		add_edge(x,y+1,INF,z); 
	}
	add_edge(s,1,INF,0);add_edge(n+1,t,INF,0); 
	MCMF(s,t);
	printf("%d\n",mincost);
	return 0; 
}