考虑把答案进行转化，通过分矩形条，我们能去掉一些夹在#之间的边

那么答案= #个数 - 能去掉的边个数

但去掉是有限制的，同一个#格子的横边和竖边不能同时去掉

把边转化成点，限制变成边。

横竖边的点 和 限制 构成了一个二分图。

问题转化成求这个二分图的最大权独立集！！

上dinic就行了

1 #include
2 #include
3 #include
4 #include
5 #include
6 #define ull unsigned long long
7 #define ll long long
8 using namespace std;
9 const int N1=200+5, inf=0x3f3f3f3f;
10 int xx[]={-1,1,0,0}, yy[]={0,0,-1,1};
11
12 template void read(_T &ret)
13 {
14 ret=0; _T fh=1; char c=getchar();
15 while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); }
16 while(c>='0'&&c<='9'){ ret=ret*10+c-'0'; c=getchar(); } 17 ret=ret*fh; 18 } 19 20 const int N2=8e4+5, M2=N2*8; 21 struct EDGE{ 22 int to[M2],nxt[M2],flow[M2],head[N2],cte; 23 void ae(int u,int v,int f) 24 { cte++; to[cte]=v, nxt[cte]=head[u]; flow[cte]=f; head[u]=cte; } 25 void adde(int u,int v,int f) 26 { ae(u,v,f); ae(v,u,0); } 27 }e; 28 int idx(char c){ return c-'0'; } 29 30 int n,m,S,T; 31 int xid[N1][N1],yid[N1][N1],tot; 32 char str[N1][N1]; 33 34 int que[N2],hd,tl,cur[N2],dep[N2]; 35 int bfs() 36 { 37 int x,j,v; 38 memset(dep,-1,sizeof(dep)); memcpy(cur,e.head,sizeof(cur)); 39 hd=1,tl=0; que[++tl]=S; dep[S]=0; 40 while(hd<=tl) 41 { 42 x=que[hd++]; 43 for(int j=e.head[x];j;j=e.nxt[j]) 44 { 45 v=e.to[j]; if(e.flow[j]<=0||dep[v]!=-1) continue; 46 dep[v]=dep[x]+1; que[++tl]=v; 47 } 48 } 49 return dep[T]!=-1; 50 } 51 int dfs(int x,int limit) 52 { 53 int j,v,flow,ans=0; 54 if(!limit||x==T) return limit; 55 for(j=cur[x];j;j=e.nxt[j]) 56 { 57 cur[x]=j; v=e.to[j]; 58 if(dep[v]==dep[x]+1 && (flow=dfs(v,min(limit,e.flow[j]))) ) 59 { 60 limit-=flow; ans+=flow; 61 e.flow[j]-=flow; e.flow[j^1]+=flow; 62 if(!limit) break; 63 } 64 } 65 return ans; 66 } 67 int Dinic() 68 { 69 int ans=0,flow; 70 while(bfs()) 71 { 72 flow=dfs(S,inf); 73 if(!flow) break; 74 ans+=flow; 75 } 76 return ans; 77 } 78 79 int main() 80 { 81 // freopen("a.in","r",stdin); 82 read(n); read(m); 83 for(int i=1;i<=n;i++) scanf("%s",str[i]+1); 84 e.cte=1; 85 for(int i=1;i>=1;
109 sumb-=Dinic();
110 printf("%d\n",suma-sumb);
111 return 0;
112 }