7月倒数第二天补flag
拆点，像深海机器人问题一样。最后求路线的时候dfs一下，根据流量判定走了几个机器人，不能超过流量即可。
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int inf=0x3f3f3f3f,N=5000005,M=5000005;
int n,p,q,g[40][40],head[N],ecnt=1,S,T,id[40][40],dis[N],from[N],num=0,l;
bool vis[N];
struct Edge{int to,nxt,val,cost,from;}e[M];
void add(int bg,int ed,int val,int cost){e[++ecnt].nxt=head[bg];e[ecnt].to=ed;e[ecnt].val=val;e[ecnt].cost=cost;e[ecnt].from=bg;head[bg]=ecnt;}
void ins(int bg,int ed,int val,int cost) {
cost=-cost;
add(bg,ed,val,cost);
add(ed,bg,0,-cost);
}
bool spfa() {
queue<int>q;
memset(dis,0x3f,sizeof dis);memset(vis,0,sizeof vis);
q.push(S);dis[S]=0;vis[S]=1;
while(!q.empty()) {
int u=q.front();q.pop();vis[u]=0;
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].to;
if(dis[v]>dis[u]+e[i].cost&&e[i].val) {
dis[v]=dis[u]+e[i].cost;from[v]=i;
if(!vis[v]) q.push(v),vis[v]=1;
}
}
}
return dis[T]!=inf;
}
int mincost,maxflow;
void mcf() {
int x=inf,i=from[T];
while(i) {x=min(x,e[i].val);i=from[e[i].from];}
i=from[T];maxflow+=x;
while(i) {e[i].val-=x;e[i^1].val+=x;mincost-=x*e[i].cost;i=from[e[i].from];}
}
void dfs(int x,int y) {
for(int i=head[id[x][y]+num];i;i=e[i].nxt) {
int v=e[i].to;
if(!e[i^1].val) continue;
if(v==id[x+1][y]) {e[i^1].val--,printf("%d %d
",l,0);dfs(x+1,y);return;}
if(v==id[x][y+1]) {e[i^1].val--,printf("%d %d
",l,1);dfs(x,y+1);return;}
}
}
int main() {
scanf("%d%d%d",&n,&q,&p);
for(int i=1;i<=p;i++)
for(int j=1;j<=q;j++)
scanf("%d",&g[i][j]),id[i][j]=++num;
S=0,T=num+num+1;
ins(S,id[1][1],n,0);ins(id[p][q]+num,T,n,0);
for(int i=1;i<=p;i++)
for(int j=1;j<=q;j++) {
if(g[i][j]==1) continue;
else if(!g[i][j]) ins(id[i][j],id[i][j]+num,inf,0);
else if(g[i][j]==2) ins(id[i][j],num+id[i][j],1,1),ins(id[i][j],num+id[i][j],inf,0);
if(g[i+1][j]!=1&&i+1<=p) ins(id[i][j]+num,id[i+1][j],inf,0);
if(g[i][j+1]!=1&&j+1<=q) ins(id[i][j]+num,id[i][j+1],inf,0);
}
while(spfa()) mcf();
for(l=1;l<=maxflow;l++)
dfs(1,1);
}