前置知识
最大费用最大流
建图
每个石头只能被获取一次,就可以考虑网络流的常规做法,把每个点拆成2个点(入点和出点)
(下面所说的连边都是双向边,网络流基础,不知道的同学建议先学习网络流)
考虑入点连向出点的边
如果这个点为障碍,那么入点不向出点连边,即这个点永远不会被经过
如果这个点不为障碍,那么入点向出点连容量为inf,代价为0的边
如果这个点为石头,那么入点向出点连容量为1,代价为1的边(容量为1保证了这个石头只被计算一次)
考虑出点连向入点的边
这种边即原图中点与点的边,从一个点的出点连向其南方和东方的点的入点即可
费用流
我们需要最多的石头,在建边时,我们将石头赋值到了边权,所以我们使用最大费用最大流
输出
跑完最大费用最大流模板后,考虑如何输出
对每个探测车进行dfs
首先要判断探测车走的方向是否正确(只能向南和东走)
其次查看这条边的反向边是否有流量,如果有,则探测车可以走这边,把这条反向边的流量-1
参考代码
#include<bits/stdc++.h> using namespace std; int k,n,m,S,T; int get(int x,int y){ return (x*m+y-1)*2; } const int N=100000,M=1000000,inf=101010; struct oppo{ int to,nex,s,w; }rod[M]; int head[N],tot; void add(int from,int to,int s,int w) { rod[tot].nex=head[from]; rod[tot].to=to; rod[tot].s=s; rod[tot].w=w; head[from]=tot++; } void link(int from,int to,int s,int w) { add(from,to,s,w); add(to,from,0,-w); } int d[N],cur[N]; bool f[N]; bool spfa() { queue<int> v; memset(f,0,sizeof(f)); memset(d,-1,sizeof(d)); d[S]=0,cur[S]=head[S]; v.push(S); while(v.size()){ int lxl=v.front();v.pop(); f[lxl]=0; for(int i=head[lxl];~i;i=rod[i].nex){ int to=rod[i].to; if(d[to]<d[lxl]+rod[i].w&&rod[i].s){ d[to]=d[lxl]+rod[i].w; cur[to]=head[to]; if(to==T) return 1; if(!f[to]){ v.push(to); f[to]=1; } } } } return 0; } bool vis[N]; int ANS; int find(int x,int low) { if(x==T){ ANS+=d[T]*low; return low; } vis[x]=1; int all=0; for(int i=cur[x];~i;i=rod[i].nex) { cur[x]=i; int to=rod[i].to; if(!vis[to]&&d[to]==d[x]+rod[i].w&&rod[i].s){ int t=find(to,min(rod[i].s,low-all)); if(!t) d[to]=-1; rod[i].s-=t; rod[i^1].s+=t; all+=t; } if(all==low) break; } vis[x]=0; return all; } void dinic() { while(spfa()) while(find(S,inf)); } void dfs(int x,int k) { if(x==T) return; for(int i=head[x];~i;i=rod[i].nex){ int to=rod[i].to; if(to>x&&rod[i^1].s){ if(x&1&&to!=T){ if(to==x+1) printf("%d 1\n",k); else printf("%d 0\n",k); } dfs(rod[i].to,k); rod[i^1].s--; return; } } } int main() { memset(head,-1,sizeof(head)); cin>>k>>m>>n; S=0,T=get(n,m)+2; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ int t; scanf("%d",&t); if(t!=1) link(get(i,j),get(i,j)^1,inf,0); if(t==2) link(get(i,j),get(i,j)^1,1,1); } getchar(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(j!=m) link(get(i,j)^1,get(i,j+1),inf,0); if(i!=n) link(get(i,j)^1,get(i+1,j),inf,0); } link(S,get(1,1),k,0); link(get(n,m)^1,T,inf,0); dinic(); for(int i=1;i<=k;i++) dfs(S,i); return 0; }