记录编号	251817	评测结果	AAAAAEEEEE
题目名称	wifi	最终得分	50
用户昵称	Satoshi	是否通过	未通过
代码语言	C++	运行时间	1.566 s
提交时间	2016-04-18 17:31:47	内存使用	0.53 MiB

#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#define N 10210
using namespace std;
ifstream in("wifi.in");
ofstream out("wifi.out");
int INF=(1<<28);
int n,m;
int S,T,O;
int ac,bc;
int val[65][65]={0};
class edge
{
public:
	int u,v,w,cap,flow;
	void make(int a,int b,int c,int d,int e)
	{
		u=a;
		v=b;
		w=c;
		cap=d;
		flow=e;
	}
	void print()
	{
		out<<u<<' '<<v<<' '<<w<<' '<<cap<<' '<<flow<<endl;
	}
};
class Dinic
{
public:
	vector<edge> E;
	vector<int> G[N];
	bool vis[N];
	int cur[N],h[N];
	int flows,size;
	void clear(int siz)
	{
		size=siz+1;
		flows=0;
		memset(vis,0,sizeof(vis));
		memset(cur,0,sizeof(cur));
		memset(h,0,sizeof(h));
		for(int i=0;i<=size;i++)G[i].clear();
		E.clear();
	}
	void add(int u,int v,int cap)
	{
		edge e;
		e.make(u,v,0,cap,0);
		//e.print();
		E.push_back(e);
		e.make(v,u,0,0,0);
		E.push_back(e);
		int o=E.size();
		G[u].push_back(o-2);
		G[v].push_back(o-1);
	}
	bool DinicBFS(int s,int t)
	{
		int i,u,v;
		queue<int> q;
		memset(vis,0,sizeof(vis));
		memset(h,0,sizeof(h));
		vis[s]=1;
		q.push(s);
		while(!q.empty())
		{
		    u=q.front();
			q.pop();
			for(i=0;i<G[u].size();i++)
			{
				edge e=E[G[u][i]];
				v=e.v;
				if(!vis[v]&&e.cap>e.flow)
				{
					vis[v]=1;
					h[v]=h[u]+1;
					q.push(v);
				}
			}
		}
		return vis[t];
	}
	int DinicDFS(int u,int a,int t)
	{
		if(u==t||a<=0)return a;
		int flow=0,d,v;
		for(int &i=cur[u];i<G[u].size();i++)
		{
			edge e=E[G[u][i]];
			v=e.v;
			if(h[v]==h[u]+1&&e.cap>e.flow)
			{
				d=DinicDFS(v,min(a,e.cap-e.flow),t);
				E[G[u][i]].flow+=d;
				E[G[u][i]^1].flow-=d;
				flow+=d;
				a-=d;
			}
			if(a<=0)break;
		}
        return flow;
	}
	int maxflow(int s,int t)
	{
		int flow=0,temp;
		while(DinicBFS(s,t))
		{
			memset(cur,0,sizeof(cur));
			temp=DinicDFS(s,INF,t);
			flow+=temp;
		}
		flows=flow;
		return flow;
	}
}A;
inline int hash(int x,int y)
{
	return (x-1)*m+y;
}
void read()
{
	int i,j,x;
	in>>n>>m>>ac>>bc;
	S=0;O=n*m;T=O+ac+bc+5;A.clear(T);
	for(i=1;i<=n;i++)for(j=1;j<=m;j++)in>>val[i][j];
}
void work()
{
	int i,j,k,x1,y1,x2,y2,z,cnt=O;
	for(k=1;k<=ac;k++)
	{
		in>>x1>>y1>>x2>>y2>>z;
		cnt++;A.add(S,cnt,z);
		for(i=x1;i<=x2;i++)for(j=y1;j<=y2;j++)A.add(cnt,hash(i,j),val[i][j]);
	}
	for(k=1;k<=bc;k++)
	{
		in>>x1>>y1>>x2>>y2>>z;
		cnt++;
		A.add(cnt,T,z);
		for(i=x1;i<=x2;i++)for(j=y1;j<=y2;j++)A.add(hash(i,j),cnt,val[i][j]);
	}
	int ans=0;
	ans=A.maxflow(S,T);
	out<<ans<<endl;
}
int main()
{
	read();
	work();
	return 0;
}