P4012 深海机器人问题

题目描述

深海资源考察探险队的潜艇将到达深海的海底进行科学考察。

潜艇内有多个深海机器人。潜艇到达深海海底后，深海机器人将离开潜艇向预定目标移动。

深海机器人在移动中还必须沿途采集海底生物标本。沿途生物标本由最先遇到它的深海机器人完成采集。

每条预定路径上的生物标本的价值是已知的，而且生物标本只能被采集一次。

本题限定深海机器人只能从其出发位置沿着向北或向东的方向移动，而且多个深海机器人可以在同一时间占据同一位置。

用一个 P×QP\times QP×Q 网格表示深海机器人的可移动位置。西南角的坐标为 (0,0)(0,0)(0,0)，东北角的坐标为 (Q,P)(Q,P)(Q,P) 。

给定每个深海机器人的出发位置和目标位置，以及每条网格边上生物标本的价值。

计算深海机器人的最优移动方案，使深海机器人到达目的地后，采集到的生物标本的总价值最高。

输入格式

文件的第 111 行为深海机器人的出发位置数 aaa,和目的地数 bbb 。

第 222 行为 PPP 和 QQQ 的值。

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

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

接下来的 aaa 行,每行有 333 个正整数 k,x,yk,x,yk,x,y,表示有 kkk 个深海机器人从 (x,y)(x,y)(x,y) 位置坐标出发。

再接下来的 bbb 行,每行有 333 个正整数 r,x,yr,x,yr,x,y ,表示有 rrr 个深海机器人可选择 (x,y)(x,y)(x,y) 位置坐标作为目的地。

a行和b行输入时横纵坐标要反过来

输出格式

输出采集到的生物标本的最高总价值.

输入输出样例

输入 #1

输出 #1

说明/提示

1≤P,Q≤151\leq P,Q\leq151≤P,Q≤15

1≤a≤41\leq a\leq 41≤a≤4

1≤b≤61\leq b\leq 61≤b≤6

思路

代码

#include<bits/stdc++.h>
#define N 10700
#define M 107000
#define inf 1<<29
using namespace std;
struct node{
    int y,z,p,next;
}e[M*2];
int tot=1,head[N],maxflow=0,ans=0;
int n,m,s,t;
void add(int x,int y,int z,int p){
    e[++tot].y=y;e[tot].z=z;e[tot].p=p;e[tot].next=head[x];head[x]=tot;
    e[++tot].y=x;e[tot].z=0;e[tot].p=-p;e[tot].next=head[y];head[y]=tot;
}
int incf[N],v[N],pre[N],d[N];
bool spfa(){
    queue<int> q;
    memset(d,0x3f,sizeof(d));// 0xcf
    memset(v,0,sizeof(v));
    q.push(s);d[s]=0;v[s]=1;
    incf[s]=inf;
    while(q.size()){
        int x=q.front();v[x]=0;q.pop();
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].y,z=e[i].z;
            if(!z) continue;
            if(d[y]>d[x]+e[i].p){//d[y]<d[x]+e[i].p
                d[y]=d[x]+e[i].p;
                incf[y]=min(incf[x],z);
                pre[y]=i;
                if(!v[y]) v[y]=1,q.push(y);
            }
        }
    }
    if(d[t]==0x3f3f3f3f) return false;//0xcfcfcfcf
    return true;
}
void update(){
    int x=t;
    while(x!=s){
        int i=pre[x];
        e[i].z-=incf[t];
        e[i^1].z+=incf[t];
        x=e[i^1].y;
    }
    maxflow+=incf[t];
    ans+=d[t]*incf[t];
}
# define pu(x,y) (x-1)*Q+y
int main()
{
    int a,b,P,Q;
    scanf("%d%d%d%d",&a,&b,&P,&Q);
    P++,Q++;s=0;t=1000;
    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);
      }
    while(spfa()) update();
    cout<<-ans<<endl;
    return 0;
}