[洛谷 3356]火星探险问题

题目链接

https://www.luogu.com.cn/problem/P3356

题解

和 [洛谷 2045]方格取数加强版 非常相似。

我们这样建模：

1. 将点 \(p\) 拆分成 \(p_x,p_y\) 两个点。
2. 对于非障碍格，从 \(p_x\) 向 \(p_y\) 连一条流量为 \(\infty\)，费用为 \(0\) 的边（表明这个格子可以经过无限次）。
3. 对于有标本的格子，从 \(p_x\) 向 \(p_y\) 连一条流量为 \(1\)，费用为 \(1\) 的边（标本只能取一次）。
4. 如果从 \(p\) 能到 \(q\)，则从 \(p_y\) 向 \(q_x\) 连一条流量为 \(\infty\)，费用为 \(0\) 的边。
5. 从源点向左上角入点 \(p_x\)，汇点向右下角出点 \(q_y\) 连一条流量为 \(n\)（只有 \(n\) 辆车），费用为 \(0\) 的边。

求最大费用最大流即可。

怎样输出方案呢？我们从起点的出点开始 DFS，枚举其向相邻点的所有边，如果一条边有流量，就将这条边的流量减去 \(1\)，跳到这个边指向的点对应的出点继续 DFS 即可。

#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
 int v,w,c,next,dir;
}e[500005];
struct node
{
 int v,e;
}p[2505];
int head[2505],dis[2505],vis[2505],a[55][55],id[55][55];
int n,k,s,t,cnt=1,maxw,tot;
void addedge(int u,int v,int w,int c,int dir=-1)
{
 e[++cnt].v=v;
 e[cnt].w=w;
 e[cnt].c=c;
 e[cnt].next=head[u];
 e[cnt].dir=dir;
 head[u]=cnt;
}
bool spfa()
{
 queue<int> q;
 memset(dis,INF,sizeof(dis));
 dis[s]=0,vis[s]=1;
 q.push(s);
 while(!q.empty())
 {
  int u=q.front();
  q.pop();
  vis[u]=0;
  for(int i=head[u];i;i=e[i].next)
   if(e[i].w&&dis[u]-e[i].c<dis[e[i].v])
   {
    dis[e[i].v]=dis[u]-e[i].c;
    p[e[i].v].v=u;
    p[e[i].v].e=i;
    if(!vis[e[i].v])
    {
     vis[e[i].v]=1;
     q.push(e[i].v);
    }
   }
 }
 return dis[t]!=INF;
}
void dfs(int id,int u)
{
 vis[u]=1,vis[u+tot]=1;
 for(int i=head[u];i;i=e[i].next)
 {
  int v=e[i].v;
  if(v==t)return;
  if(!vis[v]&&e[i^1].w)
  {
   if(e[i].dir!=-1)cout<<id<<' '<<e[i].dir<<endl;
   e[i].w++,e[i^1].w--;
   dfs(id,v+tot);
   break;
  }
 }
}
int main()
{
 int n,P,Q;
 cin>>n>>P>>Q;
 s=2*P*Q+1,t=2*P*Q+2;
 for(int i=1;i<=Q;i++)
  for(int j=1;j<=P;j++)
  {
   cin>>a[i][j];
   id[i][j]=++tot;
   if(a[i][j]!=1)
    addedge(tot,tot+P*Q,INF,0),addedge(tot+P*Q,tot,0,0);
   if(a[i][j]==2)
    addedge(tot,tot+P*Q,1,1),addedge(tot+P*Q,tot,0,-1);
  }
 addedge(s,1,n,0),addedge(1,s,0,0);
 addedge(2*P*Q,t,n,0),addedge(t,2*P*Q,0,0);
 for(int i=1;i<=Q;i++)
  for(int j=1;j<=P;j++)
  {
   int u=id[i][j],v1=id[i][j+1],v2=id[i+1][j];
   if(v1)
    addedge(u+P*Q,v1,INF,0,1),addedge(v1,u+P*Q,0,0,1);
   if(v2)
    addedge(u+P*Q,v2,INF,0,0),addedge(v2,u+P*Q,0,0,0);
  }
 while(spfa())
 {
  int minw=INF;
  for(int i=t;i!=s;i=p[i].v)
   minw=min(minw,e[p[i].e].w);
  for(int i=t;i!=s;i=p[i].v)
  {
   e[p[i].e].w-=minw;
   e[p[i].e^1].w+=minw;
  }
  maxw+=minw;
 }
 for(int i=1;i<=maxw;i++)
 {
  memset(vis,0,sizeof(vis));
  dfs(i,tot+1);
 }
 return 0;
}