P3356 火星探险问题题解

Akoasm_X · 2021-03-28 19:55:46 · 题解

网络流24题的题解我之前也有写过一些，里面也有网络流知识的教学，讲得好不好看看也无妨 传送门

12ms，发现跑得蛮快的，分享一下做法(2021.3.28)

首先这题要用到网络流就不用我多说了，题目限制了两个量：车的数量和最大的总价值。

我们把车的数量当作流量，最大总价值当作花费，就变成了最大费用最大流，接着我们在加边时把花费取负，加进去跑最小费用最大流，此时的最小费用再取负就是最大花费。当然，最大花费是多少并不重要
对于岩石标本来讲，点权为1的价值，但只能拿一次，于是我把点拆开计算，从入点向出点连边，容量为 1 ，花费为 -1。对于没有障碍的点，也从入点向出点连边，容量无穷大，但因为没有标本可以采集所以花费为0
探测车行走的话，就是从左侧/上侧的出点向右侧/下侧的入点连边，这个边对车没有限制，所以容量无穷大，花费为0
从虚拟源点向（ 1，1 ）的入点连边，容量为探测车的数量，再从（ m , n ）的出点向虚拟汇点连边，容量也是探测车的数量，花费都是0
然后愉快地跑完MCMF后，发现并不要求输出花费而是输出路径，~~行吧，下一题~~
在计算过程中会修改边的容量，修改过就表示我们走过去了，所以我就把边枚举了出来，建了个新图，跑了一遍dfs
但是也不用枚举所有边，指枚举点和点之间的连边就可以了，枚举出点，找出入点，由于这些边一开始容量都是 inf ,后来修改过程中 inf - va（现在的容量）就代表这条路径所经过的探测车有几个，那就在新图上连边，边权是 inf - va
之后就跑一边dfs就可以了,如果还是不清楚可以看代码注释

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10021;
const int maxm = 10021;
const int inf = 2147483647;
int n,m,cnt,str,end,tot = -1,maxcost,p;
int head[maxn],pre[maxn],last[maxn],flow[maxn],d[maxn],pos[50][50];
bool vis[maxn],v[maxn];
struct node
{
    int net,va,cost,to;
}data[maxm<<3];

int read() 
{
    int res=0;
    char c=getchar();
    while (c<'0'||c>'9')
        c=getchar();
    while (c>='0'&&c<='9')
    {
        res=res*10+c-'0';
        c=getchar();
    }
    return res;
}

void add(int a,int b,int va,int cost)
{
    data[++tot].cost = cost;
    data[tot].net = head[a];
    data[tot].to = b;
    data[tot].va = va;
    head[a] = tot;
    data[++tot].cost = -cost;
    data[tot].net = head[b];
    data[tot].to = a;
    data[tot].va = 0;
    head[b] = tot;
}

bool SPFA()
{
    memset(d,0x3f,sizeof(d));
    memset(flow,0x3f,sizeof(flow));
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(str);
    vis[str] = 1;
    d[str] = 0;
    pre[end] = -1;
    while(!q.empty())
    {
        int from = q.front();q.pop();
        vis[from] = 0;
        for(int i=head[from];i!=-1;i=data[i].net)
        {
            int to = data[i].to ;
            int va = data[i].va ;
            int cost = data[i].cost ;
            if(va&&d[to]>d[from]+cost)
            {
                d[to] = d[from]+cost;
                pre[to] = from; 
                last[to] = i;
                flow[to] = min(flow[from],va); 
                if(!vis[to])
                {
                    vis[to] = 1;
                    q.push(to);
                }
            }
        }
    }
    return pre[end] != -1;
}

void MCMF()
{
    while(SPFA())
    {
        int now = end;
        maxcost += flow[end]*d[end];
        while(now!=str)
        {
            data[last[now]].va -= flow[end];
            data[last[now]^1].va += flow[end];
            now = pre[now];
        }
    }
}

void print(int id,int x)
{
    int temp = x - 2 * n * m;//真实的坐标点
    for(int i=head[x];i!=-1;i=data[i].net)
    {
        int to = data[i].to ;
        int va = data[i].va ;
        if(!va) continue;//表示这条边已经不能有车通过了 
        int tt = to - 2 * n * m;
        if(temp+1==tt)  printf("%d 1\n",id);//向右 
        else            printf("%d 0\n",id);//向下 
        data[i].va--;
        print(id,to);
        break;
    }
}

int main()
{
    memset(head,-1,sizeof(head));
    cnt = read();m = read();n = read();
    str = 3 * n * m + 1;end = 3 * n * m + 2;
    //区间[1,n*m]内是入点，(n*m,2*n*m]是出点，(2*n*m,3*n*m]是新图上的点 
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            pos[i][j] = ++p;//先给每个点一个编号 
    add(str,1,cnt,0);
    add(2*n*m,end,cnt,0);//对应分析4 
    for(int i=1;i<=n;i++)//对应分析2 
    {
        for(int j=1;j<=m;j++)
        {
            int x = read();
            if(x==2)    add(pos[i][j],pos[i][j]+n*m,1,-1);
            if(x!=1)    add(pos[i][j],pos[i][j]+n*m,inf,0);
            else    v[pos[i][j]] = 1;//标记一下不能走的边 
        }
    }
    for(int i=1;i<=n;i++)//对应分析3 
        for(int j=2;j<=m;j++)
            add(pos[i][j-1]+n*m,pos[i][j],inf,0);
    for(int i=2;i<=n;i++)
        for(int j=1;j<=m;j++)
            add(pos[i-1][j]+n*m,pos[i][j],inf,0);
    MCMF();//愉快地跑一边MCMF，其中过程很常规 
    for(int x=1+n*m;x<2*n*m;x++)
    {//枚举出点 
        if(v[x-n*m])    continue;//跳过障碍 
        for(int i=head[x];i!=-1;i=data[i].net)
        {
            int va = data[i].va ;
            int to = data[i].to ;
            if(to+n*m==x)   continue;//去掉连向自身的入点 
            if(va==inf) continue;//去掉不会有车经过的边 
            if(to!=end)
                add(x+m*n,to+2*n*m,inf-va,0);
        }
    }
    for(int i=1;i<=cnt;i++)//dfs求解即可 
        print(i,1+2*n*m);
    return 0;
}

有何不当之处还请大佬指出，不妨留个赞，感谢支持！

P3356 火星探险问题 题解

12ms，发现跑得蛮快的，分享一下做法(2021.3.28)

P3356 火星探险问题题解