P3356 火星探险问题 题解
Post time: 2020-03-03 19:32:32
题目链接
网络流题目套路：
- 分析如何通过最大流/最小（大）费用来表示题目中变量。
- 根据 1 的分析建图，保证这个表示是正确的。
- 跑 HLPP/Dinic/ISAP（最大流）或者 mcmf。
一般的网络流题目，难点在第 2 步上。也不排除有些题目第一步的表示非常妙。
这道题是典型的建图题，我们会发现题目中两个变量：采集标本的数量和探测车的数量。很容易想到用最大流控制探测车，用最大费用求出最大标本数量。
考虑建图：
- \(S\to X_{1,1}\) 流量探测车数量 \(n\)，费用 \(0\)，表示初始状态。
- 拆点，\(X_{i,j}\) 和 \(Y_{i,j}\)，分别表示走到此点和走过此点。若此点有石头，则 \(X_{i,j}\to Y_{i,j}\)，流量 \(1\)，费用 \(1\)，表示取了这块石头。另外，只要这个点可以走，就连一条边\(X_{i,j}\to Y_{i,j}\)，流量 \(INF\)，费用 \(0\)，表示走过这个点。
- 点之间的连线，\(Y_{i,j}\) 到 \(X_{i+1,j}\) 和 \(X_{i,j+1}\) 分别表示向南走和向东走。
- \(Y_{p,q}\to T\)，流量 \(INF\)，费用 \(0\)，表示完成任务。
这样我们会发现，我们通过建图中的 (1) 控制了探测车数量，然后通过 (2)(3) 完成了取石头的构图。接下来就是皆大欢喜的跑 mcmf 啦！
点击查看代码
#include
#include
#include
#include
#define nm (n*m)
using namespace std;
const int N=35*35*2+5,M=35+5,INF=0x3f3f3f3f;//注意两点：maxn一定要开够；INF要小于INTmax/2，不然加起来可能会爆
struct Edge{int u,v,f,w,nxt;}e[N*2];
int h[N],pre[N],flow[N],dist[N],last[N];
bool vis[N];
int a[M][M],p[M][M];
int W,n,m,mc,mf,s,t,tot=1;
inline void add(int u,int v,int f,int w){//双向边
e[++tot]=(Edge){u,v,f,w,h[u]};h[u]=tot;
e[++tot]=(Edge){v,u,0,-w,h[v]};h[v]=tot;
}
bool spfa(){
for(int i=1;i<=nm*2+2;++i) dist[i]=-INF;
memset(flow,0x3f,sizeof(flow));
memset(vis,0,sizeof(vis));
queueq;
q.push(s);
dist[s]=0;
vis[s]=1;
pre[t]=-1;//判断能否到达汇点
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v,f=e[i].f,w=e[i].w;
if(f&&dist[v]