#6225. 「网络流 24 题」火星探险问题
内存限制：256 MiB 时间限制：1000 ms 标准输入输出
题目类型：传统 评测方式：Special Judge
上传者： 匿名
题目描述
火星探险队的登陆舱将在火星表面着陆，登陆舱内有多部障碍物探测车。
登陆舱着陆后，探测车将离开登陆舱向先期到达的传送器方向移动。
探测车在移动中还必须采集岩石标本。
每一块岩石标本由最先遇到它的探测车完成采集。
每块岩石标本只能被采集一次。
岩石标本被采集后，其他探测车可以从原来岩石标本所在处通过。
探测车不能通过有障碍的地面。
本题限定探测车只能从登陆处沿着向南或向东的方向朝传送器移动，而且多个探测车可以在同一时间占据同一位置。
如果某个探测车在到达传送器以前不能继续前进，则该车所采集的岩石标本将全部损失。
用一个 P×Q\text{P}\times \text{Q}P×Q 网格表示登陆舱与传送器之间的位置。登陆舱的位置在 (X1,Y1)(X_1,Y_1)(X1?,Y1?) 处，传送器 的位置在 (XP,YQ)(X_P,Y_Q)(XP?,YQ?) 处。 给定每个位置的状态，计算探测车的最优移动方案，使到达传送器的探测车的数量最多， 而且探测车采集到的岩石标本的数量最多。
输入格式
文件的第一行为探测车数 car\text{car}car ，第二行为 P\text{P}P 的值，第三行为 Q\text{Q}Q 的值。
接下来的 Q\text{Q}Q 行是表示登陆舱与传送器之间的位置状态的 P×Q\text{P}\times \text{Q}P×Q 网格。
用三个数字表示火星表面位置的状态：0 表示平坦无障碍，1表示障碍，2 表示石块。
输出格式
程序运行结束时，输出每个探测车向传送器移动的序列。
每行包含探测车号和一个移动方向，0 表示向南移动，1 表示向东移动。
数据范围与提示
1≤P,Q,car≤351\leq P,Q,\text{car}\leq 351≤P,Q,car≤35
题解：每个矿石只能捡一次，可以把这个点拆成两个点（入点，出点），两点连一条容量为1，费用为1的边。没障碍的点拆成两点，连接一条费用为0，流量为inf的边。 s与（1,1），（n，m）与t连一条费用为0，流量为car的边 跑最大流最大费用即可。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define oo cout<<"!!!"<<endl;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
//headconst int maxn = 1e6+11;int ver[maxn],edge[maxn],cost[maxn],nxt[maxn],head[maxn],tot;
int _edge[maxn];
int mk[44][44],mp[44][43];
int d[maxn],incf[maxn],pre[maxn],v[maxn];
int n,m,s,t,ans,maxflow;void add(int x,int y,int z,int c)
{ver[++tot] = y, edge[tot] = z;cost[tot] = c; nxt[tot] = head[x];head[x] = tot;ver[++tot] = x; edge[tot] = 0;cost[tot] = -c;nxt[tot] = head[y];head[y] = tot;
}
inline bool check(int x,int y) {return x<=n && x>=1 && y<=m &&y>=1 && mk[x][y]!=1;}bool spfa()
{queue<int>q;memset(d,0xcf,sizeof d);ms(v);q.push(s);d[s] = 0;v[s] = 1;incf[s] = inf;while(q.size()){int x = q.front();q.pop();v[x] = 0;for(int i = head[x];i;i=nxt[i]){if(!edge[i])continue;int y = ver[i];if(d[y] < d[x] + cost[i]){d[y] = d[x] + cost[i];incf[y] = min(incf[x],edge[i]);pre[y] = i;if(!v[y])q.push(y),v[y] = 1;}}}if(d[t] == 0xcfcfcfcf)return false;return true;
}void update()
{int x = t;while(x != s){int i = pre[x];edge[i] -= incf[t];edge[i^1] += incf[t];x = ver[i^1];}maxflow += incf[t];ans += d[t] * incf[t];
}bool print(int num,int x)
{ if(x == mp[n][m])return true;for(int i = head[x];i;i = nxt[i]){if(edge[i^1] && (i&1^1)){edge[i^1]--;if(ver[i] <= n*m)printf("%d %d\n",num,ver[i] == x+1-n*m);if (print(num,ver[i])) return true;}}return false;
}int main()
{tot = 1;int cnt = 0;int k;cin>>k>>m>>n;rep(i,1,n+1)rep(j,1,m+1){scanf("%d",&mk[i][j]);mp[i][j] = ++cnt;}s = n*m*2+1; t = s+1;add(s,mp[1][1],k,0);add(mp[n][m]+n*m,t,k,0);rep(i,1,n+1)rep(j,1,m+1){if(mk[i][j] == 1)continue;if(mk[i][j] == 2)add(mp[i][j],mp[i][j]+n*m,1,1);add(mp[i][j],mp[i][j]+n*m,inf,0); if(check(i+1,j)) add(mp[i][j]+n*m,mp[i+1][j],inf,0);if(check(i,j+1)) add(mp[i][j]+n*m,mp[i][j+1],inf,0);}while(spfa())update();rep(i,1,k+1)print(i,mp[1][1]);return 0;
}