题目
题目描述
深海资源考察探险队的潜艇将到达深海的海底进行科学考察。
潜艇内有多个深海机器人。潜艇到达深海海底后，深海机器人将离开潜艇向预定目标移动。
深海机器人在移动中还必须沿途采集海底生物标本。沿途生物标本由最先遇到它的深海机器人完成采集。
每条预定路径上的生物标本的价值是已知的，而且生物标本只能被采集一次。
本题限定深海机器人只能从其出发位置沿着向北或向东的方向移动，而且多个深海机器人可以在同一时间占据同一位置。
用一个$P×Q$网格表示深海机器人的可移动位置。西南角的坐标为$(0,0)$，东北角的坐标为$(Q,P)$。
给定每个深海机器人的出发位置和目标位置，以及每条网格边上生物标本的价值。
计算深海机器人的最优移动方案， 使深海机器人到达目的地后，采集到的生物标本的总价值最高。
输入输出格式
输入格式：
文件的第$1$行为深海机器人的出发位置数$a$,和目的地数$b$。
第$2$行为$P$和$Q$的值。
接下来的$P+1$行,每行有$Q$个正整数,表示向东移动路径上生物标本的价值,行数据依从南到北方向排列。
再接下来的$Q+1$行,每行有$P$个正整数,表示向北移动路径上生物标本的价值,行数据依从西到东方向排列。
接下来的$a$行,每行有$3$个正整数$k,x,y$,表示有$k$个深海机器人从$(x,y)$位置坐标出发。
再接下来的$b$行,每行有$3$个正整数$r,x,y$,表示有$r$个深海机器人可选择$(x,y)$位置坐标作为目的地。
$a$行和$b$行输入时横纵坐标要反过来
输出格式：
输出采集到的生物标本的最高总价值.
输入输出样例
输入样例#1：
1 1
2 2
1 2
3 4
5 6
7 2
8 10
9 3
2 0 0
2 2 2
输出样例#1：
42
说明
$1\le P,Q\le 15$
$1\le a\le 4$
$1\le b\le 6$
题解
很明显这是一道最大费用最大流，套用最小费用最大流的板子，只是在建图时费用为负
但是需要把图翻过来……即（样例）
然后把各个点从坐标压为一个数表示$(x-1)\times Q+y$
每个点与南边的点连两条边，一条容量为$1$，费用为标本价值（先到的机器人）
一条容量为$inf$，费用为$0$，东边同理（注意建边顺序）
源点与给出的出发点连，容量为机器人数，汇点同理，然后输出最大费用（要取负）
代码
# include<iostream>
# include<cstdio>
# include<cstring>
# include<queue>
# define pu(x,y) (x-1)*Q+y
using namespace std;
const int INF=1e8,MAX=400001,Max=1001,s=0,t=1000;
struct p{
int x,y,dis,cn;
}c[MAX];
int a,b,P,Q,num,tot1;
int h[Max],d[Max],last[Max],pre[Max];
bool use[Max];
void add(int x,int y,int dis,int cn)
{
c[num].x=h[y];c[num].y=x;c[num].dis=0,c[num].cn=-cn;h[y]=num++;
c[num].x=h[x];c[num].y=y;c[num].dis=dis,c[num].cn=cn;h[x]=num++;
}
void EK()
{
while(1)
{
queue<int> qu;
qu.push(0);
memset(d,127,sizeof(d));
d[0]=0;
while(!qu.empty())
{
int tt=qu.front();
qu.pop();
use[tt]=0;
for(int i=h[tt];i;i=c[i].x)
if(d[c[i].y]>d[tt]+c[i].cn&&c[i].dis)
{
d[c[i].y]=d[tt]+c[i].cn;
pre[c[i].y]=i;
if(!use[c[i].y])
{
use[c[i].y]=1;
qu.push(c[i].y);
}
}
}
if(d[t]>1e7) return;
int hh=t,sum=1e9;
while(pre[hh])
{
int l=pre[hh];
sum=min(sum,c[l].dis);
hh=c[l^1].y;
}
hh=t;
while(pre[hh])
{
int l=pre[hh];
c[l].dis-=sum;
c[l^1].dis+=sum;
tot1+=sum*c[l].cn;
hh=c[l^1].y;
}
}
}
int main()
{
scanf("%d%d%d%d",&a,&b,&P,&Q);
P++,Q++;
for(int i=1;i<=P;i++)
for(int j=1;j<Q;j++)
{
int x,hh=pu(i,j),tt=hh+1;
scanf("%d",&x);
add(hh,tt,1,-x);
add(hh,tt,INF,0);
}
for(int j=1;j<=Q;j++)
for(int i=1;i<P;i++)
{
int x,hh=pu(i,j),tt=hh+Q;
scanf("%d",&x);
add(hh,tt,1,-x);
add(hh,tt,INF,0);
}
for(int i=1;i<=a;i++)
{
int k,x,y;
scanf("%d%d%d",&k,&x,&y);
x++,y++;
add(s,pu(x,y),k,0);
}
for(int i=1;i<=b;i++)
{
int k,x,y;
scanf("%d%d%d",&k,&x,&y);
x++,y++;
add(pu(x,y),t,k,0);
}
EK();
printf("%d",-tot1);
return 0;
}
