题目描述

深海资源考察探险队的潜艇将到达深海的海底进行科学考察。潜艇内有多个深海机器人。潜艇到达深海海底后，深海机器人将离开潜艇向预定目标移动。深海机器人在移动中还必须沿途采集海底生物标本。沿途生物标本由最先遇到它的深海机器人完成采集。每条预定路径上的生物标本的价值是已知的，而且生物标本只能被采集一次。本题限定深海机器人只能从其出发位置沿着向北或向东的方向移动，而且多个深海机器人可以在同一时间占据同一位置。
用一个 P×Q网格表示深海机器人的可移动位置。西南角的坐标为 (0,0)，东北角的坐标为 (P,Q)。
给定每个深海机器人的出发位置和目标位置，以及每条网格边上生物标本的价值。
计算深海机器人的最优移动方案，使尽可能多的深海机器人到达目的地的前提下，采集到的生物标本的总价值最高。

题目链接：
https://www.acwing.com/problem/content/2197/

样例

略

算法1

S—>机器人出发点，所有机器人的目的地—>T，整个模型是最大费用最大流模型，边的两个端点之间需要构造两条边，一条边容量是1，费用是边的费用，一条边容量是正无穷，费用是0，用于约束每一条边的费用只被一个流量使用一次.

节点自动编号

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N=260, M=2000, inf=0x3f3f3f3f;
int ver[M],f[M],w[M],nxt[M],head[N],tot=1;
int d[N],q[N],fx[N],pre[N];
bool inq[N];
int node[20][20],m,n,S,T;

void add(int a,int b,int c,int d){
    ver[++tot]=b, f[tot]=c, w[tot]= d, nxt[tot]=head[a], head[a]=tot;
    ver[++tot]=a, f[tot]=0, w[tot]=-d, nxt[tot]=head[b], head[b]=tot;
}

bool spfa(){
    memset(d,-0x3f,sizeof d);
    fx[T]=0;
    int hh=0, tt=1;
    d[S]=0, q[0]=S, fx[S]=inf;
    while(hh!=tt){
        int t=q[hh++];
        if(hh==N)hh=0;
        inq[t]=false;
        for(int i=head[t];i;i=nxt[i]){
            int y=ver[i];
            if(!f[i] || d[t]+w[i]<=d[y])continue;
            d[y]=d[t]+w[i];
            fx[y]=min(f[i],fx[t]);
            pre[y]=i;

            if(inq[y])continue;
            inq[y]=true;
            q[tt++]=y;
            if(tt==N)tt=0;
        }
    }
    return fx[T]>0;
}

int EK(){
    int flow=0,cost=0;
    while(spfa()){
        int t=fx[T];
        flow+=t, cost+=d[T]*t;
        for(int x=T;x!=S;x=ver[pre[x]^1])
            f[pre[x]]-=t, f[pre[x]^1]+=t;
    }
    return cost;
}

int id(int i,int j){ //自动编号
    static int cnt=0;
    if(node[i][j]==0) node[i][j]=++cnt; //编号从1开始
    return node[i][j];
}

int main(){
    int A,B,c,x,y;
    cin>>A>>B>>n>>m;
    S=0, T=N-1;
    for (int i=0; i<=n; i++ )
        for (int j=0; j<m; j++ ){
            cin>>c;
            add(id(i, j), id(i, j+1), 1, c); //这样就只去1次
            add(id(i, j), id(i, j+1), inf, 0); //其它次数，无贡献
        }
    for (int i=0; i<=m; i++)
        for (int j=0; j<n; j++) {
            cin>>c;
            add(id(j, i), id(j+1, i), 1, c);
            add(id(j, i), id(j+1, i), inf, 0);
        }
    while( A-- )
        cin>>c>>x>>y,   add(S, id(x, y), c, 0); //机器人
    while( B-- )
        cin>>c>>x>>y,   add(id(x, y), T, c, 0); //目的地

    cout<<EK()<<endl;
}