狼和羊的故事。
有一个 \(n \times m\) 的网格，第 \(i\) 行第 \(j\) 列有一个数 \(a_{i,j} \in \{0,1,2\}\)。你可以沿网格线划分网格，要求划分后的每一部分不能同时出现 \(1\) 和 \(2\)。你需要最小化划分网格的网格线总长度。
\(1 \leq n,m \leq 100\)。
网络流建模。为了分割所有的 \(1\) 和 \(2\)，考虑建立源点 \(s\) 向所有的 \(1\) 连边，建立汇点 \(t\) 向所有的 \(2\) 连边，对于相邻的格子之间连边，容易发现此时的最小割就是原问题答案。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const long long INF=0x3f3f3f3f3f3f3f3f;
const int N=10000+2,M=50000;
int n,m,s,t,tot_edge;
int from[2*M+10],to[2*M+10],nxt[2*M+10];
long long cap[2*M+10];
int head[N+10],cur[N+10],level[N+10];
bool bfs(){for(int i=1;i<=n;i++){level[i]=-1;}queue<int> q;level[s]=0;q.push(s);while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];~i;i=nxt[i]){int v=to[i];if(cap[i] && level[v]==-1){level[v]=level[u]+1;q.push(v);}}}return level[t]!=-1;
}
long long dfs(int u,long long flow){if(u==t || flow==0){return flow;}long long ans=0;for(int i=cur[u];~i;i=nxt[i]){cur[u]=i;int v=to[i];if(cap[i] && level[v]==level[u]+1){long long res=dfs(v,min(flow,cap[i]));ans+=res;flow-=res;cap[i]-=res;cap[i^1]+=res;if(flow==0){break;}}}return ans;
}
long long Dinic(){long long max_flow=0;while(bfs()){for(int i=1;i<=n;i++){cur[i]=head[i];}max_flow+=dfs(s,INF);}return max_flow;
}
void add_edge(int u,int v,long long w){from[tot_edge]=u;to[tot_edge]=v;cap[tot_edge]=w;nxt[tot_edge]=head[u];head[u]=tot_edge;tot_edge++;
}
void init(){tot_edge=0;memset(nxt,-1,sizeof(nxt));memset(head,-1,sizeof(head));
}
int col[110][110],id[110][110];
int main(){init();int c_n,c_m;scanf("%d %d",&c_n,&c_m);s=++n;t=++n;for(int i=1;i<=c_n;i++){for(int j=1;j<=c_m;j++){scanf("%d",&col[i][j]);id[i][j]=++n;if(col[i][j]==1){add_edge(s,id[i][j],4);add_edge(id[i][j],s,0);}if(col[i][j]==2){add_edge(id[i][j],t,4);add_edge(t,id[i][j],0);}}}for(int i=1;i<=c_n;i++){for(int j=1;j<=c_m;j++){if(i-1>=1){add_edge(id[i][j],id[i-1][j],1);add_edge(id[i-1][j],id[i][j],0);}if(i+1<=c_n){add_edge(id[i][j],id[i+1][j],1);add_edge(id[i+1][j],id[i][j],0);}if(j-1>=1){add_edge(id[i][j],id[i][j-1],1);add_edge(id[i][j-1],id[i][j],0);}if(j+1<=c_m){add_edge(id[i][j],id[i][j+1],1);add_edge(id[i][j+1],id[i][j],0);}}}printf("%lld",Dinic());return 0;
}