啊?我没用 cin 也过了
有代码为证
```
#include <bits/stdc++.h>
#define pb push_back
#define rep(i, s, t) for(int i=(s); i<=(t); ++i)
#define F first
#define S second
#define pii pair<int, int>
#define ll long long
#define clr(x) memset(x, 0, sizeof x);
#define aint(x) x.begin(), x.end()
#define debug(x) cout<<#x<<":"<<x<<endl;
const int N=810, E=1000010, M=22, inf=0x3f3f3f3f;
using namespace std;
int n, m, s, t;
int d[N], lowi[N], hd[N];
int ver[E], nxt[E];
int edg[E];
int tot=1;
queue<int> q;
void add(int u, int v, int w)
{
ver[++tot]=v, edg[tot]=w, nxt[tot]=hd[u], hd[u]=tot;
ver[++tot]=u, edg[tot]=0, nxt[tot]=hd[v], hd[v]=tot;
}
bool bfs()
{
while(q.size()) q.pop();
rep(i, 1, t) lowi[i]=hd[i];
memset(d, 0, sizeof d);
q.push(s); d[s]=1;
while(q.size())
{
int u=q.front(); q.pop();
for(int i=hd[u], v; i; i=nxt[i])
{
if(edg[i] && !d[v=ver[i]])
{
q.push(v);
d[v]=d[u]+1;
if(v==t) return 1;
}
}
}
return 0;
}
int dinic(int u, int flow)
{
if(u==t) return flow;
int rest=flow;
for(int &i=lowi[u]; rest && i; i=nxt[i])
{
int v=ver[i];
if(edg[i] && d[v]==d[u]+1)
{
int x=dinic(v, min(rest, edg[i]));
if(x>0)
{
edg[i]-=x; edg[i^1]+=x;
rest-=x;
}
else d[v]=0;
}
}
return flow-rest;
}
int flow()
{
int ans=0;
while(bfs()) ans+=dinic(s, 2e9);
return ans;
}
int R, C, D;
char mp[M][M];
inline int num(int i, int j)
{
return (i-1)*C+j;
}
signed main()
{
scanf("%d%d%d", &R, &C, &D);
s=2*R*C+1, n=t=2*R*C+2; int base=R*C;
int totLizard=0;
rep(i, 1, R) rep(j, 1, C)
{
int lim; scanf("%1d", &lim);
add(num(i, j), base+num(i, j), lim); // 格点容量限制连边
}
rep(i, 1, R)
{
scanf("%s", &mp[i][1]);
rep(j, 1, C) if(mp[i][j]=='L')
totLizard++, add(s, num(i, j), 1); // 与初始蟋蟀连边
}
rep(i1, 1, R) rep(j1, 1, C) rep(i2, 1, R) rep(j2, 1, C)
{
if(i1==i2 && j1==j2) continue;
int x=(i1-i2)*(i1-i2)+(j1-j2)*(j1-j2);
if(x<=D*D)
add(base+num(i1, j1), num(i2, j2), inf); // 互相可达格点连边
}
rep(i, 1, R) rep(j, 1, C)
if(i+D>R || j+D>C || i-D<1 || j-D<1)
add(base+num(i, j), t, inf); // 与终点连边
printf("%d", totLizard-flow());
return 0;
}
```
by Jerrywang09 @ 2024-02-02 14:19:05