网络流24题之一。
因为石头只能取一次，因此容易想到用拆点限制。于是经典的建图，然后跑费用流。
这里说一下输出路径：用dfs随着 有流过的边 输出即可，因为我的建图点与点之间初始满流是INF，所以比INF小的就是流过的边（即有被流量），并且INF-现在的流量就是经过次数。
那么每次找完方案并把流量++即可避免重复。
细节参考代码：
#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; const int N=5000+10; const int M=50000+10; const int INF=0x3f3f3f3f; int n,m,s,t,bs,k,maxflow,mincost,mp[50][50]; struct edge{ int nxt,to,cap,cost; }edges[M<<1]; int cnt=1,head[N],pre[N]; void add_edge(int x,int y,int z,int c) { edges[++cnt].nxt=head[x]; edges[cnt].to=y; edges[cnt].cap=z; edges[cnt].cost=c; head[x]=cnt; } queue<int> q; int dis[N],lim[N]; bool inq[N]; bool spfa(int s,int t) { while (!q.empty()) q.pop(); memset(dis,0x3f,sizeof(dis)); memset(inq,0,sizeof(inq)); dis[s]=0; inq[s]=1; lim[s]=INF; q.push(s); while (!q.empty()) { int x=q.front(); q.pop(); for (int i=head[x];i;i=edges[i].nxt) { edge e=edges[i]; if (e.cap && dis[x]+e.cost<dis[e.to]) { dis[e.to]=dis[x]+e.cost; pre[e.to]=i; //即e.to这个点是从i这条边来的 lim[e.to]=min(lim[x],e.cap); if (!inq[e.to]) { q.push(e.to); inq[e.to]=1; } } } inq[x]=0; } return !(dis[t]==INF); } void MCMF() { maxflow=0; mincost=0; while (spfa(s,t)) { int now=t; maxflow+=lim[t]; mincost+=lim[t]*dis[t]; while (now!=s) { edges[pre[now]].cap-=lim[t]; edges[pre[now]^1].cap+=lim[t]; now=edges[pre[now]^1].to; } } } int id(int x,int y) { return (x-1)*m+y; } void dfs(int k,int x,int y) { //用dfs顺序输出方案 if (x==n && y==m) return; int u=id(x,y)+bs; for (int i=head[u];i;i=edges[i].nxt) { int v=edges[i].to; if (edges[i].cap<INF) { //初始流量为INF，小于INF即这条边流过 if ((v-1)/m+1>x) printf("%d %d ",k,0); else printf("%d %d ",k,1); edges[i].cap++; //重点：是他的流量++，避免下次路径重复 dfs(k,(v-1)/m+1,(v-1)%m+1); return; } } } //P3356 火星探险问题 费用流+输出路径 int main() { cin>>k>>m>>n; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&mp[i][j]); s=0; t=2*n*m+1; bs=n*m; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { if (mp[i][j]==0) add_edge(id(i,j),id(i,j)+bs,INF,0),add_edge(id(i,j)+bs,id(i,j),0,0); if (mp[i][j]==1) add_edge(id(i,j),id(i,j)+bs,0,0),add_edge(id(i,j)+bs,id(i,j),0,0); if (mp[i][j]==2) { add_edge(id(i,j),id(i,j)+bs,1,-1); add_edge(id(i,j)+bs,id(i,j),0,1); add_edge(id(i,j),id(i,j)+bs,INF,0),add_edge(id(i,j)+bs,id(i,j),0,0); } if (i<n) add_edge(id(i,j)+bs,id(i+1,j),INF,0),add_edge(id(i+1,j),id(i,j)+bs,0,0); if (j<m) add_edge(id(i,j)+bs,id(i,j+1),INF,0),add_edge(id(i,j+1),id(i,j)+bs,0,0); } add_edge(s,id(1,1),k,0); add_edge(id(1,1),s,0,0); add_edge(id(n,m),t,k,0); add_edge(t,id(n,m),0,0); MCMF(); for (int i=1;i<=maxflow;i++) dfs(i,1,1); //输出总共有maxflow个方案 return 0; }