題目描述

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

用一個 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

?

?

?

這個題目和深海機器人很像，思路差不多，就是完全按照這個坐標軸建圖就可以了。

不過有幾個地方要注意的，一個就是建圖需要用拆點，因為這個題目給的是點權，而深海機器人給的是邊權，

如果一個題目經過一個點的次數有限制，那么就需要進行拆點，如果題目給的是邊權就不需要，這個是為什么呢？

這個你可以看一下下面這個牛吃草問題，應該可以理解。

?

除了這個還有就是路徑的輸出，你需要理解一下，很容易就可以發現，這個路徑數就是最大流，

還有就是每一個點有沒有被經過，就只要看它的流量是不是>0，如果大于0，就是被經過了，否則就是沒有被經過。

這個路徑的輸出其實很好理解。

?

?

?

#include <cstdio> #include <cstdlib> #include <queue> #include <vector> #include <iostream> #include <algorithm> #include <map> #include <cstring> #include <cmath> #include <string> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int maxn = 1e5; struct edge {int u, v, c, f, cost;edge(int u, int v, int c, int f, int cost) :u(u), v(v), c(c), f(f), cost(cost) {} }; vector<edge>e; vector<int>G[maxn]; int a[maxn];//找增廣路每個點的水流量 int p[maxn];//每次找增廣路反向記錄路徑 int d[maxn];//SPFA算法的最短路 int inq[maxn];//SPFA算法是否在隊列中 int s, t; void init() {for (int i = 0; i <=maxn; i++)G[i].clear();e.clear(); } void add(int u, int v, int c, int cost) {e.push_back(edge(u, v, c, 0, cost));e.push_back(edge(v, u, 0, 0, -cost));int m = e.size();G[u].push_back(m - 2);G[v].push_back(m - 1); } bool bellman(int s, int t, int& flow, long long & cost) {memset(d, inf, sizeof(d));memset(inq, 0, sizeof(inq));d[s] = 0; inq[s] = 1;//源點s的距離設為0，標記入隊p[s] = 0; a[s] = INF;//源點流量為INF（和之前的最大流算法是一樣的） queue<int>q;//Bellman算法和增廣路算法同步進行，沿著最短路拓展增廣路，得出的解一定是最小費用最大流 q.push(s);while (!q.empty()){int u = q.front();q.pop();inq[u] = 0;//入隊列標記刪除for (int i = 0; i < G[u].size(); i++){edge & now = e[G[u][i]];int v = now.v;if (now.c > now.f && d[v] > d[u] + now.cost)//now.c > now.f表示這條路還未流滿（和最大流一樣）//d[v] > d[u] + e.cost Bellman 算法中邊的松弛 {// printf("d[%d]=%d d[%d]=%d %d d[%d]=%d\n", v,d[v],u, d[u], now.cost,v,d[u]+now.cost);// printf("\n");//printf("%d %d %d %d %d %d\n", u, now.u, now.v, now.c, now.f, now.cost);//printf("\n");d[v] = d[u] + now.cost;//Bellman 算法邊的松弛p[v] = G[u][i];//反向記錄邊的編號a[v] = min(a[u], now.c - now.f);//到達v點的水量取決于邊剩余的容量和u點的水量if (!inq[v]) { q.push(v); inq[v] = 1; }//Bellman 算法入隊 }}}if (d[t] == inf)return false;//找不到增廣路flow += a[t];//最大流的值，此函數引用flow這個值，最后可以直接求出flowcost += (long long)d[t] * (long long)a[t];//距離乘上到達匯點的流量就是費用//printf("%d %d\n", d[t], a[t]);for (int u = t; u != s; u = e[p[u]].u)//逆向存邊 {e[p[u]].f += a[t];//正向邊加上流量e[p[u] ^ 1].f -= a[t];//反向邊減去流量 （和增廣路算法一樣）//printf("e[%d]=%d e[%d]=%d\n", p[u], e[p[u]].f, p[u] ^ 1, e[p[u] ^ 1].f); }return true; } int MaxcostMaxflow(int s, int t, long long & cost) {cost = 0;int flow = 0;while (bellman(s, t, flow, cost));//由于Bellman函數用的是引用，所以只要一直調用就可以求出flow和costreturn flow;//返回最大流，cost引用可以直接返回最小費用 } int mp[110][110]; int mpp[110][110]; int n, m; void dfs(int x,int y,int u,int k) {for(int i=0;i<G[u].size();i++){int kx, ky, mov;edge &now = e[G[u][i]];if (now.v == s || now.v == u - n * m) continue;if (now.v == t) continue;if (now.f == 0) continue;now.f--;if(now.v>n*m){dfs(x, y, now.v, k);return;}if(mpp[x][y]+1==now.v){kx = x;ky = y + 1;mov = 1;}else{mov = 0;ky = y;kx = x + 1;}printf("%d %d\n", k, mov);dfs(kx, ky, now.v+n*m, k);return;} }int main() {int id = 1, k;cin >> k >> m >> n;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin >> mp[i][j];mpp[i][j] = id++;}}int s = 0, t = 2 * n * m + 1;if (mp[1][1] != 1) add(s, mpp[1][1], k, 0);if (mp[n][m] != 1) add(mpp[n][m] + n * m, t, k, 0);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if (mp[i][j] == 1) continue;add(mpp[i][j], mpp[i][j] + n * m, inf, 0);if (mp[i][j] == 2){add(mpp[i][j], mpp[i][j] + n * m, 1, -1);}if(i!=1&&mp[i-1][j]!=1){add(mpp[i - 1][j] + n * m, mpp[i][j], inf, 0);}if(j!=1&&mp[i][j-1]!=1){add(mpp[i][j - 1] + n * m, mpp[i][j], inf, 0);}}}ll cost = 0;int ans = MaxcostMaxflow(s, t, cost);for(int i=1;i<=ans;i++){dfs(1, 1, 1, i);}return 0; }

?

轉載于:https://www.cnblogs.com/EchoZQN/p/10797861.html

總結

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

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