思路和题解一样

蜜汁WA 9pts

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1005,M=100005;
int p,q,a,b,s=1001,t=1002,head[N],pre[N],flowa[N],lst[N],cnt=1;
int dis[N],result,maxflow;//我是伞兵
bool vis[N];
inline int minn(int a,int b)
{
	if(a<b)
		return a;
	else
		return b;
}
inline int read()
{
	int f=0,w=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
			w=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		f=f*10+c-'0';
		c=getchar();
	}
	return w*f;
}
inline int id(int x,int y)
{
	return q*(x-1)+y;
}
struct edge
{
	int u,v,w,c,next;
}e[M<<1];
void addedge(int u,int v,int w,int c)
{
	e[++cnt].next=head[u];
	head[u]=cnt;
	e[cnt].u=u;
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].c=c;
}
bool SPFA()//最大费用最大流 
{
	memset(dis,inf,sizeof(dis));
	memset(vis,false,sizeof(vis));
	memset(flowa,inf,sizeof(flowa));
	queue <int> Q;
	Q.push(s);
	dis[s]=0;
	vis[s]=true;
	pre[t]=-1;
	while(!Q.empty())
	{
		int u=Q.front();
		for(int i=head[u];i;i=e[i].next)
			if(dis[e[i].v]>dis[u]+e[i].c&&e[i].w)
			{
				int v=e[i].v;
				pre[v]=u;
				dis[v]=dis[u]+e[i].c;
				lst[v]=i;
				flowa[v]=minn(flowa[u],e[i].w);
				if(!vis[v])
				{
					vis[v]=true;
					Q.push(v);
				}
			}
		vis[u]=false;
		Q.pop();
	}
	if(pre[t]==-1)
		return false;
	else
		return true;
}
void Dinic()
{
	while(SPFA())
	{
		int u=t;
		result+=flowa[t]*dis[t];
		maxflow+=flowa[t];
		while(u!=s)
		{
			e[lst[u]].w-=flowa[t];
			e[lst[u]^1].w+=flowa[t];
			u=pre[u];
		}
	}
}
int main()
{
	int valuel,k,x,y;
	a=read();b=read();p=read();q=read();
	p++;q++;
	for(int i=1;i<=p;i++)
		for(int j=1;j<=q-1;j++)
		{
			valuel=read();
			addedge(id(i,j),id(i,j+1),1,-valuel);
			addedge(id(i,j+1),id(i,j),0,valuel);
			addedge(id(i,j),id(i,j+1),inf,0);
			addedge(id(i,j+1),id(i,j),0,0);
		}
	for(int i=1;i<=p-1;i++)
		for(int j=1;j<=q;j++)
		{
			valuel=read();
			addedge(id(i,j),id(i+1,j),1,-valuel);
			addedge(id(i+1,j),id(i,j),0,valuel);
			addedge(id(i,j),id(i+1,j),inf,0);
			addedge(id(i+1,j),id(i,j),0,0);
		}
	for(int i=1;i<=a;i++)
	{
		k=read();x=read();y=read();
		x++,y++;
		addedge(s,id(y,x),k,0);
		addedge(id(y,x),s,0,0);
	}
	for(int i=1;i<=b;i++)
	{
		k=read();x=read();y=read();
		x++,y++;
		addedge(id(y,x),t,k,0);
		addedge(t,id(y,x),0,0);
	}
	Dinic();
	printf("%d",-result);
	return 0;
}