題目描述

火星探險隊的登陸艙將在火星表面著陸，登陸艙內有多部障礙物探測車。登陸艙著陸后，探測車將離開登陸艙向先期到達的傳送器方向移動。探測車在移動中還必須采集巖石標本。每一塊巖石標本由最先遇到它的探測車完成采集。每塊巖石標本只能被采集一次。巖石標本被采集后，其他探測車可以從原來巖石標本所在處通過。探測車不能通過有障礙的地面。本題限定探測車只能從登陸處沿著向南或向東的方向朝傳送器移動，而且多個探測車可以在同一時間占據同一位置。如果某個探測車在到達傳送器以前不能繼續前進，則該車所采集的巖石標本將全部損失。

用一個 P·Q 網格表示登陸艙與傳送器之間的位置。登陸艙的位置在(X1,Y1)處，傳送器

的位置在(XP ,YQ)處。

X 1,Y 1 X 2 , Y 1 X 3 , Y 1 ... X P-1, Y 1 X P , Y 1

X 1,Y 2 X 2 , Y 2 X 3 , Y 2 ... X P-1, Y 2 X P , Y 2

X 1, Y 3 X 2 , Y 3 X 3 ,Y 3 ... X P-1, Y 3 X P , Y 3

... ...

X 1 ,Y Q-1 X 2 , Y Q-1 X 3 , Y Q-1 ... X P-1, Y Q-1 X P , Y Q-1

X 1,Y Q X 2 , Y Q X 3 , Y Q ... X P-1, Y Q X P ,Y Q

給定每個位置的狀態，計算探測車的最優移動方案，使到達傳送器的探測車的數量最多，

而且探測車采集到的巖石標本的數量最多

輸入輸出格式

輸入格式：

?

第 1行為探測車數，第 2 行為 P 的值，第3 行為Q 的值。接下來的 Q 行是表示登陸艙與傳送器之間的位置狀態的 P·Q 網格。用 3 個數字表示火星表面位置的狀態：0 表示平坦無障礙，1表示障礙，2 表示石塊。

?

輸出格式：

?

每行包含探測車號和一個移動方向，0 表示向南移動，1 表示向東移動。

?

輸入輸出樣例

輸入樣例#1：?復制 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：?復制 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

說明

車數,P,Q<=35

?

這題與深海機器人問題

不過也有不同

首先此問題是點權，因此我們考慮拆點

另外這題需要輸出方案

我們考慮利用發現邊的性質：反向邊有多少流量，就代表這個點被經過了多少次

因此我們可以利用反向邊來統計出該點的經過次數

然后枚舉每一個車，讓其沿邊走就好

?

#include<cstdio> #include<cstring> #include<queue> #include<algorithm> #include<vector> #include<cmath> #define AddEdge(x,y,z,f) add_edge(x,y,z,f),add_edge(y,x,-z,0) using namespace std; const int MAXN=1e5+10; const int INF=1e8+10; inline int read() {char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; } int N,M,K,S,T; int anscost=0; struct node {int u,v,w,f,nxt; }edge[MAXN]; int head[MAXN],num=2; inline void add_edge(int x,int y,int z,int f) {edge[num].u=x;edge[num].v=y;edge[num].w=z;edge[num].f=f;edge[num].nxt=head[x];head[x]=num++; } int Pre[MAXN],vis[MAXN],dis[MAXN]; bool SPFA() {queue<int>q;memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));dis[S]=0;q.push(S);while(q.size()!=0){int p=q.front();q.pop();vis[p]=0;for(int i=head[p];i!=-1;i=edge[i].nxt){if(dis[edge[i].v]>dis[p]+edge[i].w&&edge[i].f){dis[edge[i].v]=dis[p]+edge[i].w;Pre[edge[i].v]=i;if(!vis[edge[i].v])vis[edge[i].v]=1,q.push(edge[i].v);}}}return dis[T]<=INF; } void f() {int nowflow=INF;for(int now=T;now!=S;now=edge[Pre[now]].u)nowflow=min(nowflow,edge[Pre[now]].f);for(int now=T;now!=S;now=edge[Pre[now]].u)edge[Pre[now]].f-=nowflow,edge[Pre[now]^1].f+=nowflow;anscost+=nowflow*dis[T]; } void MCMF() {int ans=0;while(SPFA())f(); } int point=0; int belong[1001][1001],can[1001][1001]; main() {#ifdef WIN32freopen("a.in","r",stdin);#else#endifmemset(head,-1,sizeof(head));K=read();M=read();N=read();for(int i=1;i<=N;i++)for(int j=1;j<=M;j++)belong[i][j]=++point;for(int i=1;i<=N;i++)for(int j=1;j<=M;j++){int opt=read();if(opt==2) AddEdge(belong[i][j],belong[i][j]+point,-1,1);if(opt!=1) AddEdge(belong[i][j],belong[i][j]+point,0,INF);if(i<N) AddEdge(belong[i][j]+point,belong[i+1][j],0,INF);if(j<M) AddEdge(belong[i][j]+point,belong[i][j+1],0,INF);}S=0;T=point*4;AddEdge(S,belong[1][1],0,K);AddEdge(belong[N][M]+point,T,0,K);MCMF();for(int i=1;i<=N;i++)for(int j=1;j<=M;j++)for(int k=head[belong[i][j]];k!=-1;k=edge[k].nxt)if(edge[k].v==belong[i][j]+point)can[i][j]+=edge[k^1].f;for(int kk=1;kk<=K;kk++){int xx=1,yy=1;while(xx!=N||yy!=M){if(can[xx+1][yy]) printf("%d 0\n",kk),can[xx][yy]--,xx++;else printf("%d 1\n",kk),can[xx][yy]--,yy++;}}return 0; }

?

總結

以上是生活随笔為你收集整理的洛谷P3356 火星探险问题(费用流)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。