题解

该题是基于最小费用最大流算法的网格路径问题。在n×m网格中，部分格子为源点（mp[i][j]=1），部分为汇点（mp[i][j]=2），其余为普通格子。源点可无限流出，汇点可无限流入，每个格子仅能通过一次。将每个格子抽象为图节点，源点连接所有源点格子（容量INF，费用0），汇点连接所有汇点格子（容量INF，费用0），普通格子向四邻接格子连边（容量1，费用0）。使用ISAP算法（BFS层次图+DFS找增广路）求解最大流，结果即为最多可通过的格子数。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6,inf=0x3f3f3f3f;
struct edge{int x,y,flow,cost,pre;}a[N];
int alen,last[N];
void ins(int x,int y,int flow,int cost){
	a[++alen]={x,y,flow,cost,last[x]};last[x]=alen;
	a[++alen]={y,x,0,-cost,last[y]};last[y]=alen;
}
int st,ed;
int h[N];
bool spfa(){
	queue<int> q;q.push(st);
	memset(h,0,sizeof(h));h[st]=1;
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int k=last[x];k;k=a[k].pre){
			int y=a[k].y;
			if(a[k].flow>0&&!h[y]){
				h[y]=h[x]+1;
				q.push(y);
			}
		}
	}
	return h[ed]>0;
}
int cur[N];
int findflow(int x,int f){
	if(x==ed) return f;
	int sx=0;
	for(int k=cur[x];k;k=a[k].pre){
		cur[x]=k;
		int y=a[k].y;
		if(a[k].flow>0&&h[y]==h[x]+1&&sx<f){
			int sy=findflow(y,min(f-sx,a[k].flow));
			sx+=sy;
			a[k].flow-=sy;a[k^1].flow+=sy;
		}
	}
	if(sx==0) h[x]=-1;
	return sx;
}
int mp[110][110];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int main(){
	alen=1;
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&mp[i][j]);
		}
	}
	st=n*m+1;ed=st+1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(mp[i][j]==1) ins(st,(i-1)*m+j,inf,0);
			if(mp[i][j]==2) ins((i-1)*m+j,ed,inf,0);
			for(int k=0;k<4;k++){
				int x=i+dx[k],y=j+dy[k];
				if(x>n||x<=0||y>m||y<=0) continue;
				ins((i-1)*m+j,(x-1)*m+y,1,0);
			}
		}
	}
	int res=0;
	while(spfa()){
		memcpy(cur,last,sizeof(last));
		res+=findflow(st,inf);
	}
	printf("%d",res);
}