记录编号	379776	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]你猜是不是DP	最终得分	100
用户昵称	可以的.	是否通过	通过
代码语言	C++	运行时间	1.718 s
提交时间	2017-03-07 17:03:03	内存使用	22.51 MiB

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <ctime>
#define IL inline
#define RG register
#define Mem(a, v) memset(a, v, sizeof a)
using namespace std;
IL void qkin(RG int &res){
	RG int x,f=1; RG char ch;
	while(ch=getchar(),ch<'0'||ch>'9')if(ch=='-')f=-1;x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;res=x*f;}
IL void read(RG int &A){ qkin(A); }
IL void read(RG int &A,RG int &B){ qkin(A),qkin(B); }
IL void read(RG int &A,RG int &B,RG int &C){ qkin(A),qkin(B),qkin(C); }
const int maxn = 41000;
const int inf = 0x7f7f7f7f;
int n,m,B[10010],W[10010];
int tot;
int now;
int len,head[maxn],S,T;
struct Edge
{
	int from,to,next,flow;
}e[maxn*40];
int ansflow;
IL void ins(int,int,int);
IL void insert(int,int,int);
bool BFS();
int DFS(int,int);
IL void Dinic();
#define lson lc[rt],l,mid
#define rson rc[rt],mid+1,r
int rta,rtb;
int lc[maxn],rc[maxn],cnt;
int id[maxn];
IL void build(int &rt,int l,int r){
	rt = ++cnt;
	if(l == r){
		id[l] = rt;
		return;
	}
	int mid = (l+r)>>1;
	build(lson); build(rson);
	insert(rt, lc[rt], inf);
	insert(rt, rc[rt], inf);
}
IL void rebuild(int &rt,int l,int r){
	if(l == r){
		rt = id[l];
		return;
	}
	rt = ++cnt;
	int mid = (l+r)>>1;
	rebuild(lson); rebuild(rson);
	insert(lc[rt], rt, inf);
	insert(rc[rt], rt, inf);
}
IL void Add(int s,int t,int rt,int l,int r){
	if(s <= l && t >= r){
		insert(now, rt, inf);
		return;
	}
	int mid = (l+r)>>1;
	if(s <= mid) Add(s, t, lson);
	if(t  > mid) Add(s, t, rson);
}
IL void re_add(int s,int t,int rt,int l,int r){
	if(s <= l && t >= r){
		insert(rt, now, inf);
		return;
	}
	int mid = (l+r)>>1;
	if(s <= mid) re_add(s, t, lson);
	if(t  > mid) re_add(s, t, rson);
}
int main(){
#define HAHA LALA
#ifdef HAHA
    freopen("nicai.in","r",stdin);
    freopen("nicai.out","w",stdout);
#endif
	Mem(head, -1);
	read(n, m);
	build(rta,1,n);
	rebuild(rtb,1,n);
	S = cnt + 1, T = S + 1; now = T;
	for(int i = 1; i <= n; i ++ ){
		read(B[i]);
	}
	for(int i = 1; i <= n; i ++ ){
		read(W[i]);
		tot += W[i];
		if(B[i]-W[i] >= 0) insert(S, id[i], B[i]-W[i]), tot += B[i]-W[i];
		else insert(id[i], T, W[i]-B[i]);
	}
	RG int op,s,t,c;
	
	for(int i = 1; i <= m; i ++ ){
		read(op, s); read(t, c);
		now ++ ; tot += c;
		if(op == 1){
			insert(S, now, c);
			Add(s,t,rta,1,n);
		} else { 
			insert(now, T, c);
			re_add(s,t,rtb,1,n);
		}
	}
	Dinic();
	//printf("ansflow = %d\n", ansflow);
	RG int ans = tot - ansflow;
	printf("%d\n", ans);
 
	 // printf("time = %f\n", (double)clock()/CLOCKS_PER_SEC);
 
	return 0;
}
 
IL void ins(int x,int y,int z){
	e[len].from = x;
	e[len].to = y;
	e[len].flow = z;
	e[len].next = head[x];
	head[x] = len++;
}
IL void insert(int x,int y,int z){
	ins(x, y, z); ins(y, x, 0);
}
int dis[maxn],q[maxn],h,r;
bool BFS(){
	h = r = 0;
	q[r++] = S;
	Mem(dis, -1); 
	dis[S] = 0;
	while(h != r){
		int k = q[h++];
		for(int i = head[k]; i!=-1; i = e[i].next){
			int p = e[i].to;
			if(dis[p] < 0 && e[i].flow > 0){
				dis[p] = dis[k]+1;
				q[r++] = p;
			}
		}
	}
	if(dis[T] < 0) return false;
	else return true;
}
int cur[maxn];
int DFS(int x,int low){
	if(x == T || !low) return low;
	int flow=0, f;
	for(int &i = cur[x]; i!=-1; i = e[i].next){
		int p = e[i].to;
		if(dis[p] == dis[x]+1){
			f = DFS(p, min(e[i].flow, low));
			if(!f) continue;
			e[i].flow -= f; e[i^1].flow += f;
			low -= f; flow += f;
			if(!low) break;
		}
	}
	return flow;
}
#define Mcpy(a, b) memcpy(a, b, sizeof a)
IL void Dinic(){
	ansflow = 0;
	while( BFS() ){
		Mcpy(cur, head);
		ansflow += DFS(S, inf);
	}
}