记录编号	152995	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 深海机器人	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2015-03-16 15:10:20	内存使用	0.41 MiB

#include<iostream>
#include<cstdio>
using namespace std;
#define INF 1e9
int a,b,i,j,p,k,q,zj1,zj2,ans,ST,SD;
int to[5400]={0},ne[5400]={0},w[5400]={0},r[5400]={0},head[450]={0},sj=1;
inline void addedge(int u,int v,int z,int R)
{
	to[++sj]=v,ne[sj]=head[u],head[u]=sj,w[sj]=-z,r[sj]=R;
	to[++sj]=u,ne[sj]=head[v],head[v]=sj,w[sj]=z,r[sj]=0;
}
void init()
{
	scanf("%d%d%d%d",&a,&b,&p,&q);
	ST=(p+1)*(q+1)+1,SD=ST+1;
	for(i=0;i<=p;i++)for(j=0;j<=q;j++)
	{
		if(j<q)addedge(i*(q+1)+j+1,i*(q+1)+j+2,0,INF);
		if(i<p)addedge(i*(q+1)+j+1,(i+1)*(q+1)+j+1,0,INF);
	}
	for(i=0;i<=p;i++)for(j=1;j<=q;j++)
	{
		scanf("%d",&zj1);
		addedge(i*(q+1)+j,i*(q+1)+j+1,zj1,1);
	}
	for(j=0;j<=q;j++)for(i=0;i<p;i++)
	{
		scanf("%d",&zj1);
		addedge(i*(q+1)+j+1,(i+1)*(q+1)+j+1,zj1,1);
	}
	for(i=1;i<=a;i++)
	{
		scanf("%d%d%d",&k,&zj1,&zj2);
		addedge(ST,zj1*(q+1)+zj2+1,0,k);
	}
	for(i=1;i<=b;i++)
	{
		scanf("%d%d%d",&k,&zj1,&zj2);
		addedge(zj1*(q+1)+zj2+1,SD,0,k);
	}
}
 
int que[450]={0},qtail=0,qhead=1;bool flag[450]={0};
inline void PUSH(int &x)
{que[0]++;flag[x]=1;if(++qtail==450)qtail=1;que[qtail]=x;}
inline int GET()
{int x=que[qhead];flag[x]=0;que[0]--;if(++qhead==450)qhead=1;return x;}
 
int dis[450]={0},pre[450]={0},pres[450]={0};
inline bool spfa()
{
	for(i=1;i<=SD;i++)dis[i]=INF;
	dis[ST]=0;PUSH(ST);
	while(que[0])
	{
		zj1=GET();
		for(i=head[zj1];i;i=ne[i])
		if(r[i]&&(dis[to[i]]>(zj2=dis[zj1]+w[i])))
		{
			dis[to[i]]=zj2,pre[to[i]]=zj1,pres[to[i]]=i;
			if(!flag[to[i]])PUSH(to[i]);
		}
	}
	if(dis[SD]==INF)return 0;
	return 1;
}
 
void work()
{
	for(zj1=SD;zj1!=ST;zj1=pre[zj1])
	r[pres[zj1]]--,r[pres[zj1]^1]++;
	ans+=dis[SD];
}
int main()
{
	freopen("shinkai.in","r",stdin);
	freopen("shinkai.out","w",stdout);
	init();
	while(spfa())work();
	printf("%d\n",-ans);
	return 0;
}