记录编号	251835	评测结果	AAAAAAAEEE
题目名称	wifi	最终得分	70
用户昵称	Fmuckss	是否通过	未通过
代码语言	C++	运行时间	2.630 s
提交时间	2016-04-18 18:00:38	内存使用	172.35 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 3e4;
const int inf = 1e9;

int s, t;
int n, m, a, b;
int ma[65][65];

class solve_max_flow {
private:
	struct edge {
		int to, ne, le;
		edge() {}
		edge(int to_, int ne_, int le_) { to = to_, ne = ne_, le = le_; }
	}e[maxn*(int)5e2];
	int head[maxn], tot;
	int de[maxn];
	int cur[maxn];
public:
	void add_edge(int fr, int to, int v) {
		e[++tot] = edge(to, head[fr], v); head[fr] = tot;
		e[++tot] = edge(fr, head[to], 0); head[to] = tot;
	}
	
	bool bfs() {
		memset(de, 0, sizeof(de));
		queue<int> q;
		q.push(s);
		de[s] = 1;
		while(!q.empty()) {
			int now = q.front(); q.pop(); 
			if(now == t) return true;
			for(int i = head[now]; i; i = e[i].ne) {
				int to = e[i].to;
				if(de[to] || e[i].le <= 0) continue;
				de[to] = de[now] + 1;
				q.push(to);
			}
		}
		return de[t];
	}
	
	int dfs(int now, int min_flow) {
		if(now == t) return min_flow;
		
		for(int &i = cur[now]; i; i = e[i].ne) {
			int to = e[i].to;
			if(de[to] != de[now] + 1 || e[i].le <= 0) continue;
			int now_flow = dfs(to, min(min_flow, e[i].le));
			if(!now_flow) continue;
			e[i].le -= now_flow;
			if(i & 1) e[i+1].le += now_flow;
			else e[i-1].le += now_flow;
			return now_flow;
		}
		return 0; 
	}
	
	int solve() {
		int ans = 0, tmp;
		while(bfs()) {
			memcpy(cur, head, (t+1) << 2);
			while(tmp = dfs(s, inf)) ans += tmp;
		}
		return ans;
	}
	
}smf;

int get_num() {
	int ans = 0;
	char tmp = getchar();
	while(tmp < '0' || tmp > '9') tmp = getchar();
	while(tmp >= '0' && tmp <= '9') {
		ans = 10*ans + tmp - '0';
		tmp = getchar();
	} 
	return ans;
}

int hash[65][65];

void get_hash() {
	int cnt = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			hash[i][j] = ++cnt;
		}
	}
}

void read() {
	n = get_num();
	m = get_num();
	a = get_num();
	b = get_num();
	int p = n*m;
	s = 2*p + a+b + 1;
	t = s + 1;
	get_hash();
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			ma[i][j] = get_num();
			smf.add_edge(hash[i][j], p + hash[i][j], ma[i][j]);
		}
	}
	int x1, x2, y1, y2, c;
	for(int i = 1; i <= a; i++) {
		x1 = get_num();
		y1 = get_num();
		x2 = get_num();
		y2 = get_num();
		c = get_num();
		smf.add_edge(s, i + p*2, c);
		for(int j = x1; j <= x2; j++) {
			for(int k = y1; k <= y2; k++) {
				smf.add_edge(i + p*2, hash[j][k], inf);
			}
		}
	}
	for(int i = 1; i <= b; i++) {
		x1 = get_num();
		y1 = get_num();
		x2 = get_num();
		y2 = get_num();
		c = get_num();
		smf.add_edge(a + i + p*2, t, c);
		for(int j = x1; j <= x2; j++) {
			for(int k = y1; k <= y2; k++) {
				smf.add_edge(p + hash[j][k], a + i + p*2, inf);
			}
		}
	}
}

int main() {
	freopen("wifi.in", "r", stdin);
	freopen("wifi.out", "w", stdout);
	read();
	printf("%d", smf.solve());
	return 0;	
}