网页链接 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;
}