C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 504K, 提交时间: 2022-11-09 22:39:19

#include<bits/stdc++.h>
using namespace std;

const int MAXN=305;
const int MAXM=1e5+5;
const int INF=1e8;
struct EDGE
{
    int to,nxt,flow,cost;
}edge[MAXM];
int head[MAXN],tot=1;
int pre[MAXN],incf[MAXN],dis[MAXN];
bool vis[MAXN];
int s,t,maxcost;
int a,b,n,m;
void add(int x,int y,int z,int c)
{
    edge[++tot]=(EDGE){y,head[x],z,c},head[x]=tot;
    edge[++tot]=(EDGE){x,head[y],0,-c},head[y]=tot;
}
bool spfa()
{
    queue<int>q;
    memset(dis,-0x3f,sizeof(dis));
    q.push(s),dis[s]=0,vis[s]=1,incf[s]=INF;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=edge[i].nxt)
        {
            int y=edge[i].to,z=edge[i].flow,c=edge[i].cost;
            if(dis[y]<dis[x]+c && z)
            {
                dis[y]=dis[x]+c,incf[y]=min(incf[x],z),pre[y]=i;
                if(!vis[y]) q.push(y),vis[y]=1;
            }
        }
    }
    return dis[t]!=dis[0];
}
void update()
{
    int x=t;
    while(x!=s)
    {
        int i=pre[x];
        edge[i].flow-=incf[t],edge[i^1].flow+=incf[t];
        x=edge[i^1].to;
    }
    maxcost+=dis[t]*incf[t];
}
int pos(int x,int y){return (x-1)*m+y;}
int main()
{
    cin>>a>>b>>n>>m;
    ++n,++m;
    s=n*m+1,t=n*m+2;
    int x,y,w;
    for(int i=1;i<=n;++i) for(int j=2;j<=m;++j) scanf("%d",&w),add(pos(i,j-1),pos(i,j),1,w),add(pos(i,j-1),pos(i,j),INF,0);
    for(int j=1;j<=m;++j) for(int i=2;i<=n;++i) scanf("%d",&w),add(pos(i-1,j),pos(i,j),1,w),add(pos(i-1,j),pos(i,j),INF,0);
    for(int i=1;i<=a;++i) scanf("%d %d %d",&w,&x,&y),add(s,pos(x+1,y+1),w,0);
    for(int i=1;i<=b;++i) scanf("%d %d %d",&w,&x,&y),add(pos(x+1,y+1),t,w,0);
    while(spfa()) update();
    cout<<maxcost;
    return 0;
}
/*
1 1
2 2
1 2
3 4
5 6
7 2
8 10
9 3
3 0 0
3 2 2
*/