題目描述

火星探險(xiǎn)隊(duì)的登陸艙將在火星表面著陸，登陸艙內(nèi)有多部障礙物探測(cè)車。登陸艙著陸后，探測(cè)車將離開(kāi)登陸艙向先期到達(dá)的傳送器方向移動(dòng)。

探測(cè)車在移動(dòng)中還必須采集巖石標(biāo)本。每一塊巖石標(biāo)本由最先遇到它的探測(cè)車完成采集。每塊巖石標(biāo)本只能被采集一次。巖石標(biāo)本被采集后，其他探測(cè)車可以從原來(lái)巖石標(biāo)本所在處通過(guò)。探測(cè)車不能通過(guò)有障礙的地面。

本題限定探測(cè)車只能從登陸處沿著向南或向東的方向朝傳送器移動(dòng)，而且多個(gè)探測(cè)車可以在同一時(shí)間占據(jù)同一位置。如果某個(gè)探測(cè)車在到達(dá)傳送器以前不能繼續(xù)前進(jìn)，則該車所采集的巖石標(biāo)本將全部損失。

用一個(gè)?p \times qp×q?網(wǎng)格表示登陸艙與傳送器之間的位置。登陸艙的位置在?(x_1,y_1)(x1?,y1?)?處，傳送器的位置在?(x_py_q)(xp?yq?)?處。

\begin{bmatrix} (x_1,y_1) & (x_2,y_1) & \dots & (x_{p-1},y_1) & (x_p,y_1) \\ (x_1,y_2) & (x_2,y_2) & \dots & (x_{p-1},y_2) & (x_p,y_2) \\ \dots & \dots & \dots & \dots & \dots \\ (x_1,y_{q-1}) & (x_2,y_{q-1}) & \dots & (x_{p-1},y_{q-1}) & (x_p,y_{q-1}) \\ (x_1,y_q) & (x_2,y_q) & \dots & (x_{p-1},y_q) & (x_p,y_q) \end{bmatrix}????????(x1?,y1?)(x1?,y2?)…(x1?,yq?1?)(x1?,yq?)?(x2?,y1?)(x2?,y2?)…(x2?,yq?1?)(x2?,yq?)?……………?(xp?1?,y1?)(xp?1?,y2?)…(xp?1?,yq?1?)(xp?1?,yq?)?(xp?,y1?)(xp?,y2?)…(xp?,yq?1?)(xp?,yq?)?????????

給定每個(gè)位置的狀態(tài)，計(jì)算探測(cè)車的最優(yōu)移動(dòng)方案，使到達(dá)傳送器的探測(cè)車的數(shù)量最多，而且探測(cè)車采集到的巖石標(biāo)本的數(shù)量最多。

輸入格式

第一行為探測(cè)車數(shù)?nn，接下來(lái)兩行分別為?p,qp,q。

接下來(lái)的?qq?行是表示登陸艙與傳送器之間的位置狀態(tài)的?p \times qp×q?網(wǎng)格。
用三種數(shù)表示火星表面位置的狀態(tài)：00?表示平坦無(wú)障礙，11?表示障礙，22?表示石塊。

輸出格式

每行包含探測(cè)車號(hào)和一個(gè)移動(dòng)方向，00?表示向南移動(dòng)，11?表示向東移動(dòng)。

輸入輸出樣例

輸入 #1復(fù)制

2 10 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 2 0 0 0 0 1 1 0 1 2 0 0 0 0 1 0 1 0 0 2 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 0 1 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0

輸出 #1復(fù)制

1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 0 2 1 2 1 2 1 2 1 2 0 2 0 2 0 2 0 2 1 2 0 2 0 2 1 2 0 2 1 2 1 2 1

說(shuō)明/提示

【數(shù)據(jù)范圍】 對(duì)于?100\%100%?的數(shù)據(jù)，1 \le n,p,q \le 351≤n,p,q≤35。

?

?這題面比英文都難看?

解釋一下8還是：

p?* q的平面，(1, 1)點(diǎn)有 n 個(gè)小車，只能向下或向右走，終點(diǎn)為 (p, q)。格點(diǎn)有3個(gè)狀態(tài)，0為平坦，1為障礙物，2為石塊。障礙物無(wú)法通行，其余地方同一時(shí)間內(nèi)可有多輛小車，石塊處可選擇采集石塊，同一石塊只能被采集一次，問(wèn)小車的移動(dòng)方案，使得到達(dá)終點(diǎn)的小車最多，而且采集到的石塊最多

思路：

把小車的數(shù)量當(dāng)作流量，采集石塊的數(shù)量當(dāng)作費(fèi)用（取負(fù)值），每個(gè)位置拆成一個(gè)出點(diǎn)和一個(gè)入點(diǎn)，建邊：

（1）除障礙物外的所有點(diǎn)，入點(diǎn)連出點(diǎn)，流量為inf，費(fèi)用為0

（2）有石塊的點(diǎn)，入點(diǎn)連出點(diǎn)，流量為1，費(fèi)用為-1（一塊石頭最多采集一次，費(fèi)用為其貢獻(xiàn)值 -1）

（3）超級(jí)源點(diǎn)連(1, 1)的入點(diǎn)，流量為小車數(shù)量，費(fèi)用為0

（4）（p, q）的出點(diǎn)連超級(jí)匯點(diǎn)，流量為小車數(shù)量，費(fèi)用為0

（5）小車向右移動(dòng)：左邊點(diǎn)的出點(diǎn)連右邊點(diǎn)的入點(diǎn)，流量為inf，費(fèi)用為0

（6）小車向下移動(dòng)：上邊點(diǎn)的出點(diǎn)連下邊點(diǎn)的入點(diǎn)，流量為inf，費(fèi)用為0

dfs輸出路徑

……代碼轉(zhuǎn)自https://12349.blog.luogu.org/solution-p3356

#include<cstdio> #include<queue> #include<iostream> #include<cstring> using namespace std;#define nxt(x) (x+m*n) #define INF 0x3f3f3f3f int cur=1,n,m,s,t,mcost,mflow,car,ID; int head[5005],dis[5005],flow[5005],pre[5005]; int Map[105][105],p[105][105]; struct EDGE{int t,next,w,f; }e[100005]; void add(int a,int b,int w,int f) {cur++;e[cur].t=b;e[cur].next=head[a];e[cur].w=w;e[cur].f=f;head[a]=cur;cur++;e[cur].t=a;e[cur].next=head[b];e[cur].w=0;e[cur].f=-f;head[b]=cur; }queue < int > q; bool vis[5005]; bool SPFA(int s,int t) {memset(dis,0x3f,sizeof dis);memset(vis,0,sizeof vis);dis[s]=0;vis[s]=1;flow[s]=INF;q.push(s);while (!q.empty()){int u=q.front();q.pop();vis[u]=false;for (int h=head[u];h!=-1;h=e[h].next){int v=e[h].t,f=e[h].f;if (e[h].w&&dis[u]+f<dis[v])//如果邊還有流量就嘗試更新{dis[v]=dis[u]+f;//更新最短路徑flow[v]=min(flow[u],e[h].w);//盡可能地流水pre[v]=h;//記錄路徑if (!vis[v]){vis[v]=true;q.push(v);}}}}return dis[t]!=INF; }void Update(int s,int t) {int x=t;while (x!=s){int i=pre[x];e[i].w-=flow[t];e[i^1].w+=flow[t];x=e[i^1].t;}//沿著記錄下的路徑并進(jìn)行增廣路mflow+=flow[t];mcost+=flow[t]*dis[t];//累計(jì)費(fèi)用 } void E_K(int s,int t) {while (SPFA(s,t))//當(dāng)還有多余流量時(shí)Update(s,t); }void dfs(int x,int y,int u,int k) {int kx,ky,mov;for (int h=head[u];h!=-1;h=e[h].next){int v=e[h].t;if (v==s) continue;if (v==t) continue;if (v==u-n*m) continue;if (!e[h^1].w) continue;e[h^1].w--;if (v>n*m){dfs(x,y,v,k);return;}if (v==p[x][y]+1){kx=x;ky=y+1;mov=1;}else{kx=x+1;ky=y;mov=0;}printf("%d %d\n",k,mov);dfs(kx,ky,v+n*m,k);return;} } int main() {scanf("%d%d%d",&car,&m,&n);s=0;t=n*m*2+1;memset(head,-1,sizeof head);for (int i=1;i<=n;i++)for (int j=1;j<=m;j++){scanf("%d",&Map[i][j]);p[i][j]=++ID;}if (Map[1][1]!=1) add(s,1,car,0);if (Map[n][m]!=1) add(nxt(p[n][m]),t,car,0);for (int i=1;i<=n;i++)for (int j=1;j<=m;j++){if (Map[i][j]==1) continue;add(p[i][j],nxt(p[i][j]),INF,0);if (Map[i][j]==2)add(p[i][j],nxt(p[i][j]),1,-1);if (Map[i+1][j]!=1&&p[i+1][j]){add(nxt(p[i][j]),p[i+1][j],INF,0);}if (Map[i][j+1]!=1&&p[i][j+1]){add(nxt(p[i][j]),p[i][j+1],INF,0);}}E_K(s,t);for (int i=1;i<=mflow;i++)dfs(1,1,1,i);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的luogu P3356 火星探险问题（网络流24题 拆点 + 最小费用流 + 路径输出）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。