洛谷 P4012 深海机器人问题 题解【网络流】【费用流】

作者: wjyyy 分类: 网络流,解题报告,费用流 发布时间: 2019-01-15 18:46

点击量:27

费用流方格取数型题。

题目描述

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

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

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

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

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

用一个\(P\times 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)\)位置坐标作为目的地。

输出格式:

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

输入输出样例

输入样例#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\leq P,Q\leq15\)

\(1\leq a\leq 4\)

\(1\leq b\leq 6\)

题解:

说是“方格取数”类问题,实际上每个点、每条边是可以经过多次的。我们直接按图上网格建边就可以了,方向是\(\rightarrow,\uparrow\)。

但是重点是每条边只在第一次被经过时产生收益,这个看来是不好在费用流中进行特判的了。

如果这些边的容量全部设为\(1\),那么一条边就不能被经过第二次了,这当\(\sum k+\sum r\)很大的时候会存在机器人跑不过去的情况。

如果这些边的容量为\(\inf\),那么不容易判断这条边是第几次被经过,而且残量网络也不方便更新。

此时我们可以建两条边,一条是带费用的,容量为\(1\),另一条是不带费用的,容量为\(\inf\)。但是这两条边的优先级怎么确定呢?

由于费用流的特殊性,EK费用流是通过spfa来增广的,当存在上述带费用的边时,会先跑带费用的边(最大费用最大流中权值实际为负)。此时就既解决了收益最大化问题,也解决了收益单次性问题。

不过像bzoj 1001/洛谷 P4001 狼抓兔子这一题的建模就更考察思维了。

Code:

#include<queue>
#include<cstdio>
#include<cstring>
#define s 290
#define t 291
using std::queue;
struct edge
{
    int n,nxt,v,w;
    edge(int n,int nxt,int v,int w)
    {
        this->n=n;
        this->nxt=nxt;
        this->v=v;
        this->w=w;
    }
    edge(){}
}e[2000];
int head[300],ecnt=-1;
void add(int from,int to,int v,int w)
{
    e[++ecnt]=edge(to,head[from],v,w);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to],0,-w);
    head[to]=ecnt;
}
int dis[300],pre[300];
bool used[300];
bool spfa()
{
    memset(dis,0x3f,sizeof(dis));
    queue<int> q;
    q.push(s);
    used[s]=1;
    dis[s]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        used[x]=0;
        for(int i=head[x];~i;i=e[i].nxt)
            if(e[i].v&&dis[e[i].n]>dis[x]+e[i].w)
            {
                dis[e[i].n]=dis[x]+e[i].w;
                pre[e[i].n]=i;
                if(!used[e[i].n])
                {
                    used[e[i].n]=1;
                    q.push(e[i].n);
                }
            }
    }
    return dis[t]!=0x3f3f3f3f;
}
int main()
{
    memset(head,-1,sizeof(head));
    int a,b,n,m,u,v,w;
    scanf("%d%d%d%d",&a,&b,&n,&m);
    for(int i=0;i<=n;++i)
        for(int j=0;j<m;++j)
        {
            scanf("%d",&u);
            add(i*(m+1)+j,i*(m+1)+j+1,1,-u);
            add(i*(m+1)+j,i*(m+1)+j+1,0x3fffffff,0);
        }
    for(int i=0;i<=m;++i)
        for(int j=0;j<n;++j)
        {
            scanf("%d",&u);
            add(j*(m+1)+i,(j+1)*(m+1)+i,1,-u);
            add(j*(m+1)+i,(j+1)*(m+1)+i,0x3fffffff,0);
        }
    for(int i=1;i<=a;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(s,v*(m+1)+w,u,0);
    }
    for(int i=1;i<=b;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(v*(m+1)+w,t,u,0);
    }
    int ans=0;
    pre[s]=-1;
    while(spfa())
    {
        int p=pre[t],mn=0x3fffffff;
        while(~p)
        {
            mn=mn<e[p].v?mn:e[p].v;
            p=pre[e[p^1].n];
        }
        p=pre[t];
        while(~p)
        {
            e[p].v-=mn;
            e[p^1].v+=mn;
            ans+=e[p].w*mn;
            p=pre[e[p^1].n];
        }
    }
    printf("%d\n",-ans);
    return 0;
}

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 题解 […]

/* */