记录编号	251821	评测结果	AAAAAATEEE
题目名称	wifi	最终得分	60
用户昵称	mikumikumi	是否通过	未通过
代码语言	C++	运行时间	4.577 s
提交时间	2016-04-18 17:35:37	内存使用	79.71 MiB

#include<cstdio>
#include<vector>
#include<deque>
#include<iostream>
#include<algorithm>
using namespace std;
const int SIZEN=60,INF=0x7fffffff/2,SIZEP=10010,SIZEM=300100;
int N,M;
int a,b;
vector<int> s[SIZEM];
int w[SIZEN][SIZEN];
int id[SIZEN][SIZEN];
class miku
{
public:
	int fr,to,cap,flow;
	miku(){}
	miku(int a,int b,int c,int d)
	{
		fr=a;to=b;cap=c;flow=d;
	}
}E[SIZEM*16];
class poi
{
public:
	int x1,y1,x2,y2;
	int z;
}A[SIZEP],B[SIZEP];
int tot=0;
void add(int fr,int to,int cap)
{
	s[fr].push_back(tot);E[tot++]=miku(fr,to,cap,0);
	s[to].push_back(tot);E[tot++]=miku(to,fr,0,0);
}
void read()
{
	scanf("%d%d%d%d",&N,&M,&a,&b);
	int now=0;
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=M;j++)
		{
			id[i][j]=++now;
			scanf("%d",&w[i][j]);
		}
	}
	for(int i=1;i<=a;i++) scanf("%d%d%d%d%d",&A[i].x1,&A[i].y1,&A[i].x2,&A[i].y2,&A[i].z);
	for(int i=1;i<=b;i++) scanf("%d%d%d%d%d",&B[i].x1,&B[i].y1,&B[i].x2,&B[i].y2,&B[i].z);
}
int S,T;
void make_gragh()
{
	int P=N*M;
	S=0;T=P*2+a+b+1;
	//cout<<T<<endl;
	for(int i=1;i<=a;i++)
	{
		add(S,P*2+i,A[i].z);
		for(int j=A[i].x1;j<=A[i].x2;j++)
		{
			for(int k=A[i].y1;k<=A[i].y2;k++)
				add(P*2+i,id[j][k],INF);
		}
	}
	for(int i=1;i<=b;i++)
	{
		add(P*2+a+i,T,B[i].z);
		for(int j=B[i].x1;j<=B[i].x2;j++)
		{
			for(int k=B[i].y1;k<=B[i].y2;k++)
				add(id[j][k]+P,P*2+a+i,INF);
		}
	}
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=M;j++) add(id[i][j],id[i][j]+P,w[i][j]);
	}
}
int e[SIZEM],H[SIZEM];
deque<int> Q;
void push(int x,int t)
{
	miku &v=E[t];
	int flow=min(e[x],v.cap-v.flow);
	e[x]-=flow;v.flow+=flow;
	E[t^1].flow-=flow;e[v.to]+=flow;
	//cout<<v.to<<" "<<flow<<endl;
	if(v.to!=S&&v.to!=T&&e[v.to]) Q.push_back(v.to);
}
void use_up(int x)
{
	int mi;
	while(e[x])
	{
		mi=INF;
		//cout<<x<<" "<<e[x]<<endl;
		for(int i=0;i<s[x].size();i++)
		{
			miku &v=E[s[x][i]];
			if(v.cap<=v.flow) continue;
			if(H[x]-1==H[v.to])
			{
				push(x,s[x][i]);
				if(!e[x]) break;
			}
			else mi=min(mi,H[v.to]);
		}
		if(!e[x]) break;
		H[x]=mi+1;
	}
}
int maxflow()
{
	e[S]=INF;
	H[S]=10;
	for(int i=0;i<s[S].size();i++) push(S,s[S][i]);
	while(!Q.empty())
	{
		int x=Q.front();Q.pop_front();
		//cout<<x<<endl;
		use_up(x);
	}
	return e[T];
}
int main()
{
	freopen("wifi.in","r",stdin);
	freopen("wifi.out","w",stdout);
	read();
	make_gragh();
	int ans=maxflow();
	printf("%d\n",ans);
	return 0;
}