|
flow=0; for (;;) { dinic_bfs(s); if (lv[t]<0) break; memcpy(iter,fir,sizeof iter); int _f; while ((_f=dinic_dfs(s,t,INF))>0) total_flow+=_f; } return total_flow; } int main() { #ifdef FCBRUCE freopen(/home/fcbruce/code/t,r,stdin); #endif // FCBRUCE int T_T; scanf( %d,&T_T); while (T_T--) { int n,m,s=0,t=8963; scanf( %d%d,&n,&m); e_max=0; memset(fir,-1,sizeof fir); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { add_edge(i*m+j+n*m,i*m+j,1); if (i==n || j==m) continue; add_edge(i*m+j,(i+1)*m+j+n*m,1); add_edge(i*m+j,i*m+j+1+n*m,1); add_edge((i+1)*m+j,i*m+j+n*m,1); add_edge(i*m+j+1,i*m+j+n*m,1); } for (int i=1;i<=m;i++) { add_edge(1*m+i,t,1); add_edge(n*m+i,t,1); } for (int i=2;i
?
|