网页链接 https://www.luogu.org/problemnew/show/4012

做题背景

在不久的将来,人工智能发展使得人类大量失业,也使得现在的我们做[深海机器人问题]做得想死...

准备工作

确实是一个很难的题目呢,要是做不出来,你可以选择看一看另一道题

https://www.luogu.org/problemnew/show/2045

这叫方格取数加强版(虽然说实话这道题跟方格取数没有关系)

也是深海机器人的弱化版

其实方格取数加强版的思路跟深海机器人是一样的,只是实现上深海机器人更困难

所以看完我的思路之后建议你先去做方格取数再来做它

做法

跑最大流最大费用流

你只需要按题目所给的去连边(方格取数加强版给边给的很清楚,深海机器人有些模糊,不懂看下面)

但是题目给你的两点之间要连两种边

1.一条 流量为1 费用为 价值×(-1) (因为要求最大费用)

2.一条 流量为INF 费用为 0

第一种边显然是经过并采集标本,所以只能走一次

第二种显然是经过但标本被采完,所以可以无限走

最后,也是最简单的,就是把

s -> 起点 流量为人数 费用为0

终点->t 流量为人数,费用为0

这就不用解释了吧.

如果你看不懂题目（其实我一开始也没看懂）看这里

以下是原话

ｉｎｐｕｔ１－－－接下来的 P+1 行,每行有 Q 个正整数,表示向东移动路径上生物标本的价值,行数据依从南到北方向排列。

ｉｎｐｕｔ２－－－再接下来的 Q+1 行,每行有 P 个正整数,表示向北移动路径上生物标本的价值,行数据依从西到东方向排列。

结合洛谷上的图看我给你的坐标图

先分析input1，它是这么连边的

（０，０）－＞（１，０）－＞．．．（ｑ，０）

（０，１）－＞（１，１）－＞．．．（ｑ，１）

　。。。。。。。。。。。。。。。。。。。。。。

（０，ｐ）－＞（１，ｐ）－＞．．．（ｑ，ｐ）

你会发现所给的数据有p+1行　（０，０）　＝＞　（０，ｐ）

每行有q+1个点　（０，Ｘ） => （ｑ，Ｘ）

所以每行有q条边(边数＝点数－１)

所以是p+1行一行ｑ个

～～ｉｎｐｕｔ２同理可得～～

代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <vector>

#include <queue>

#define rg register int

#define il inline

#define INF 2147483647

#define SZ 10000000

#define pos(x,y) (x+(y-1)*(X+1))

using namespace std;

int p,q,s,t,Ans=0;

il int gi()

{

    int q=0,w=1;char c=getchar();

    while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}

    while(isdigit(c))q=q*10+c-'0',c=getchar();

    return w*q;

}

struct Edge{int to,nxt,w,c;}e[5001];

int Ehead[5001],pe[5001],Ecnt=2;

il void Eadd(int u,int v,int w,int c)

{

    e[Ecnt]=(Edge){v,Ehead[u],w,c};

    Ehead[u]=Ecnt++;

    e[Ecnt]=(Edge){u,Ehead[v],0,-c};

    Ehead[v]=Ecnt++;

}

int dis[5001];

bool vis[5001];

queue <int> Q;

il bool spfa()

{

    for(rg i=1;i<=t;++i) dis[i]=INF;

    dis[s]=0;Q.push(s);

    while(!Q.empty())

    {

        rg u=Q.front();Q.pop();

        for(rg i=Ehead[u];i;i=e[i].nxt)

        {

            rg v=e[i].to;

            if((e[i].w&&dis[v]>dis[u]+e[i].c))

            {

                dis[v]=dis[u]+e[i].c;

                pe[v]=i;

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

            }

        }

        vis[u]=0;

    }

    if(dis[t]==INF) return 0;

    int di=INF;

    for(rg i=t;i^s;i=e[pe[i]^1].to)

     di=min(di,e[pe[i]].w);

    Ans-=di*dis[t];

    for(rg i=t;i^s;i=e[pe[i]^1].to)

     e[pe[i]].w-=di,e[pe[i]^1].w+=di;

    return 1;

}

int A,B,k,x,y,X,Y,a;

int main()

{

    cin>>A>>B>>Y>>X;

    s=0;t=(X+1)*(Y+1)+1;

    for(rg i=1;i<=Y+1;++i)

     for(rg j=1;j<=X;++j)

     {

     	 a=gi();

     	 Eadd(pos(j,i),pos(j+1,i),1,-a);

     	 Eadd(pos(j,i),pos(j+1,i),INF,0);

     }

    for(rg i=1;i<=X+1;++i)

     for(rg j=1;j<=Y;++j)

     {

         a=gi();

         Eadd(pos(i,j),pos(i,j+1),1,-a);

         Eadd(pos(i,j),pos(i,j+1),INF,0);

     }

    for(rg i=1;i<=A;++i)

    {

        k=gi(),x=gi(),y=gi();

        Eadd(s,pos(y+1,x+1),k,0);

    }

    for(rg i=1;i<=B;++i)

    {

        k=gi(),x=gi(),y=gi();

        Eadd(pos(y+1,x+1),t,k,0);

    }

    while(spfa());

    cout<<Ans;

    return 0;

}