火星探险队的登陆舱将在火星表面着陆，登陆舱内有多部障碍物探测车。登陆舱着陆后，探测车将离开登陆舱向先期到达的传送器方向移动。
探测车在移动中还必须采集岩石标本。每一块岩石标本由最先遇到它的探测车完成采集。每块岩石标本只能被采集一次。岩石标本被采集后，其他探测车可以从原来岩石标本所在处通过。探测车不能通过有障碍的地面。
本题限定探测车只能从登陆处沿着向南或向东的方向朝传送器移动，而且多个探测车可以在同一时间占据同一位置。如果某个探测车在到达传送器以前不能继续前进，则该车所采集的岩石标本将全部损失。
用一个 p \times qp×q 网格表示登陆舱与传送器之间的位置。登陆舱的位置在 (x_1,y_1)(x1,y1) 处，传送器的位置在 (x_py_q)(xpyq) 处。
\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)⎦⎥⎥⎥⎥⎥⎤
给定每个位置的状态，计算探测车的最优移动方案，使到达传送器的探测车的数量最多，而且探测车采集到的岩石标本的数量最多。
第一行为探测车数 nn，接下来两行分别为 p,qp,q。
接下来的 qq 行是表示登陆舱与传送器之间的位置状态的 p \times qp×q 网格。 用三种数表示火星表面位置的状态：00 表示平坦无障碍，11 表示障碍，22 表示石块。
每行包含探测车号和一个移动方向，00 表示向南移动，11 表示向东移动。
输入 #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【数据范围】 对于 100\%100% 的数据，1 \le n,p,q \le 351≤n,p,q≤35。
这题面比英文都难看
解释一下8还是：
p * q的平面，(1, 1)点有 n 个小车，只能向下或向右走，终点为 (p, q)。格点有3个状态，0为平坦，1为障碍物，2为石块。障碍物无法通行，其余地方同一时间内可有多辆小车，石块处可选择采集石块，同一石块只能被采集一次，问小车的移动方案，使得到达终点的小车最多，而且采集到的石块最多
思路：
把小车的数量当作流量，采集石块的数量当作费用（取负值），每个位置拆成一个出点和一个入点，建边：
（1）除障碍物外的所有点，入点连出点，流量为inf，费用为0
（2）有石块的点，入点连出点，流量为1，费用为-1（一块石头最多采集一次，费用为其贡献值 -1）
（3）超级源点连(1, 1)的入点，流量为小车数量，费用为0
（4）（p, q）的出点连超级汇点，流量为小车数量，费用为0
（5）小车向右移动：左边点的出点连右边点的入点，流量为inf，费用为0
（6）小车向下移动：上边点的出点连下边点的入点，流量为inf，费用为0
dfs输出路径
……代码转自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; }//沿着记录下的路径并进行增广路 mflow+=flow[t]; mcost+=flow[t]*dis[t];//累计费用 } void E_K(int s,int t) { while (SPFA(s,t))//当还有多余流量时 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; }
