题意
给出一个 \(n\times m\) 个六边形的网格，字符画形式给出，每两个格子之间可能有墙或无墙，问对每对不同的点来说使它们不连通增加的墙数量之和为多少。
\(n,m\le 100\)，六边不全为墙的格子数量 \(\le 3000\)。
思路
最大的一坨。
对每对不同的点求最小割，显然最小割树，直接模拟建图即可。
又因最大答案不超过 \(6\)，所以跑网络流不会超时。
注意不要用 ISAP，会死的很惨。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace mf{const int N=3010,INF=0x3f3f3f3f;struct node{int ed,w,id;};vector<node>e[N];int n,S,T;int dep[N],now[N];void init(int nn){for(int i=1;i<=nn;i++)e[i].clear();n=nn;}bool bfs(){memset(dep,-1,sizeof(dep));queue<int>q;q.push(S);dep[S]=0;while(!q.empty()){int t=q.front();q.pop();for (int i=0;i<e[t].size();i++){int ed=e[t][i].ed;if (dep[ed]==-1&&e[t][i].w){dep[ed]=dep[t]+1;q.push(ed);}}}memset(now,0,sizeof(now));return dep[T]!=-1;}int dfs(int st, int lim){if(st==T)return lim;for(int i=now[st];i<e[st].size();i++){now[st]=i;int ed=e[st][i].ed;if(dep[ed]==dep[st]+1&&e[st][i].w){int tmp=dfs(ed,min(e[st][i].w,lim));if(tmp){e[st][i].w-=tmp;e[ed][e[st][i].id].w+=tmp;return tmp;}}}return 0;}int dinic(){int r=0,flow;while(bfs())while(flow=dfs(S,INF))r+=flow;return r;}void add(int st,int ed,int w){int sti=e[st].size();int edi=e[ed].size();e[st].push_back({ed,w,edi});e[ed].push_back({st,0,sti});}
}
namespace go{struct node{int x,y,w;};vector<node> yt,t[3005];void add(int x,int y,int v){yt.push_back({x,y,v});}int n,a[3005],tmp[3005],dep[3005],f[3005],ans;bool can[3005];void build(int l,int r){if(l>=r) return;mf::init(n);int x=a[l],y=a[r];mf::S=x,mf::T=y;for(node v:yt)mf::add(v.x,v.y,v.w),mf::add(v.y,v.x,v.w);int w=mf::dinic();t[x].push_back({y,w});t[y].push_back({x,w});int tl=l-1,tr=r+1;for(int i=l;i<=r;i++){if(mf::dep[a[i]]!=-1) tmp[++tl]=a[i];else tmp[--tr]=a[i];}for(int i=l;i<=r;i++)a[i]=tmp[i];build(l,tl);build(tr,r);}void dfs(int x,int fa){if(f[x]!=0x3f3f3f3f) ans+=f[x];for(node v:t[x])if(v.x!=fa)f[v.x]=min(f[x],v.y),dfs(v.x,x);}
}
int T,n,m,id[1005][1005],tot;
string s[3005];
signed main(){cin>>T;for(int I=1;I<=T;I++){tot=0;go::yt.clear();go::ans=0;cin>>n>>m;cin.ignore();for(int i=1;i<=4*n+3;i++){getline(cin,s[i]);}for(int i=1;i<=4*n+3;i++){for(int j=0;j<s[i].length();j++){if(s[i][j]=='*') id[i][j]=++tot;}}for(int i=2;i<=4*n+3;i++){for(int j=1;j<s[i].length();j++){if(s[i-1][j-1]=='+'&&s[i+1][j+1]=='+'&&s[i][j]==' '){go::add(id[i+1][j-3],id[i-1][j+3],1);}if(s[i+1][j-1]=='+'&&s[i-1][j+1]=='+'&&s[i][j]==' '){go::add(id[i-1][j-3],id[i+1][j+3],1);}if(j>1&&j<s[i].length()-2&&s[i][j-2]=='+'&&s[i][j+2]=='+'&&s[i][j]==' '){go::add(id[i-2][j],id[i+2][j],1);}}}for(int i=1;i<=tot;i++)go::t[i].clear();go::n=tot;for(int i=1;i<=tot;i++)go::a[i]=i;go::build(1,tot);for(int i=1;i<=tot;i++)go::f[i]=0x3f3f3f3f,go::dfs(i,0);cout<<"Case #"<<I<<": "<<go::ans/2<<endl;}return 0;
}