记录编号	66766	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2013] 防守战线	最终得分	100
用户昵称	lazycal	是否通过	通过
代码语言	C++	运行时间	3.585 s
提交时间	2013-07-31 22:07:13	内存使用	0.78 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <deque>
#include <queue>
const int N = 1000 + 9, M = 10000 + 9,INF = 0x3f3f3f40;
int ec,son[N],dis[N],n,m,src,sink,times,pre[N];
int vis[N];
struct node
{
	int u,v,c,f,next;
}es[2*(N + M + N)];
inline void addedge(const int x,const int y,const int z,const int w)
{
	es[ec].v=y; es[ec].u=x;
	es[ec].f=z; es[ec].c=w;
	es[ec].next=son[x]; son[x]=ec++;
}
inline void Addedge(const int x,const int y,const int z,const int w = 0){addedge(x,y,z,w);addedge(y,x,0,-w);}
int sap(const int u,const int aug)
{
	if (u == sink) return aug;
	vis[u] = times;
	int sum = 0;
	for (int i = son[u]; i != -1; i = es[i].next) {
		const int v = es[i].v;
		if (vis[v] != times && es[i].f && dis[u] - es[i].c == dis[v]) {
			int t = sap(v,std::min(aug - sum,es[i].f));
			sum += t; es[i].f -= t; es[i^1].f += t;
			if (sum == aug) return sum;
		}
	}
	return sum;
}
bool spfa()
{
	static std::deque<int> q;
	static bool inq[N];
	memset(dis,0xc0,sizeof dis);
	memset(pre,0,sizeof pre);
	dis[sink] = 0;
	inq[sink] = 1;
	for (q.push_front(sink);!q.empty();) {
		int u = q.front();
		q.pop_front();
		for (int i = son[u]; i != -1; i = es[i].next) {
			const int v = es[i].v;
			if (es[i^1].f && dis[v] < dis[u] - es[i].c) {
				dis[v] = dis[u] - es[i].c;
				pre[v] = u;
				if (!inq[v]) {
					inq[v] = 1;
					if (q.empty() || dis[q.front()] < dis[v]) q.push_front(v);
					else q.push_back(v);
				}
			}
		}
		inq[u] = 0;
	}
	return dis[src] != -INF;
}
int ZKW_CF()
{
	int ans = 0,t;
	while (spfa()) 
		while (++times,t = sap(src,INF)) ans += t * dis[src];
	return ans;
}
int main()
{
	freopen("zjoi13_defend.in","r",stdin);
	freopen("zjoi13_defend.out","w",stdout);
	scanf("%d%d",&n,&m);
	memset(son,-1,sizeof son);
	src = 0; sink = n + 2;
	int last,now = 0;
	for (int i = 1; i <= n; ++i) {
		Addedge(i+1,i,INF);
		last = now;
		scanf("%d",&now);
		if (last - now > 0) Addedge(src,i,last - now);
		else Addedge(i,sink,- last + now);
	}
	Addedge(src,n + 1,now);
	for (int i = 1,l,r,v; i <= m; ++i) {
		scanf("%d%d%d",&l,&r,&v);
		Addedge(r+1,l,INF,v);
	}
	printf("%d\n",ZKW_CF());
}