luogu P4012 深海机器人问题

luogu P4012 深海机器人问题

// luogu-judger-enable-o2

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define INF 0x7fffffff

const int maxn = 2007;

using std::min;

using std::queue;

int dis[maxn];bool vis[maxn];

inline int read() {

    int x=0,f=1;

    char c=getchar() ;

    while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();

    return x*f;

}

int S,T,n,m,pre[maxn],Min_Cost;

struct node{

    int u,v,cost,flow,next;

}edge[(maxn*10)<<1];

int num=1,head[maxn];

void add_edge(int u,int v,int w,int cost)  {

    edge[++num].v=v;edge[num].u=u;edge[num].flow=w;edge[num].cost=cost,edge[num].next=head[u],head[u]=num;

}

bool spfa() {

    memset(vis,0,sizeof vis);

    memset(dis,0x3f,sizeof dis);

    queue<int>que;

    que.push(S);vis[S]=1,dis[S]=0;

    while(!que.empty())  {

        int x=que.front();que.pop();

        for(int i=head[x];i;i=edge[i].next ) {

            int v=edge[i].v;

            if(dis[x]+edge[i].cost<dis[v]&&edge[i].flow>0) {

                pre[v]=i;

                dis[v]=dis[x]+edge[i].cost;

                if(!vis[v])vis[v]=1,que.push(v);

            }

        }

        vis[x]=0;

    }

    return dis[T]!=0x3f3f3f3f;

}

void calc() {

    int MF=0x3f3f3f3f;

    for(int i=T;i!=S;i=edge[pre[i]].u)

        MF=min(MF,edge[pre[i]].flow);

    for(int i=T;i!=S;i=edge[pre[i]].u) {

        edge[pre[i]].flow-=MF;

        edge[pre[i]^1].flow+=MF;

        Min_Cost+=edge[pre[i]].cost*MF;

    }

}

void MFMC() {

    while(spfa())

    calc();

}

void Add(int u,int v,int flow,int cost) {

    add_edge(u,v,flow,cost);

    add_edge(v,u,0,-cost);

}

int loc[30][32];

int main() {

    n=read(),m=read();int P=read()+1;int Q=read()+1;

    S=0,T=P*Q+1;

    for(int cnt=0,i=1;i<=P;i++)

        for(int j=1;j<=Q;j++)

            loc[i][j]=++cnt;

    for(int i=1;i<=P;i++)

        for(int j=1;j<=Q-1;j++)

            Add(loc[i][j],loc[i][j+1],1,-read()),

            Add(loc[i][j],loc[i][j+1],INF,0);

    for(int j=1;j<=Q;j++)

        for(int i=1;i<=P-1;i++)

            Add(loc[i][j],loc[i+1][j],1,-read()),

            Add(loc[i][j],loc[i+1][j],INF,0);

    for(int a,b,c,i=1;i<=n;i++) {

        a=read(),b=read(),c=read();

        Add(S,loc[b+1][c+1],a,0);

    }

    for(int a,b,c,i=1;i<=m;i++) {

        a=read(),b=read(),c=read();

        Add(loc[b+1][c+1],T,a,0);

    }

    MFMC();

    printf("%d\n",-Min_Cost);

    return 0;

}