显然是个最小割嘛！
一开始我是这么建图的：
- 源点向狼连INF
- 羊向汇点连INF
- 每两个相邻格子间连双向边，边权为1
然后T成狗
后来我是这么建图的：
- 源点向狼连INF
- 羊向汇点连INF
- 狼和空地向相邻的非狼节点连1
然后跑得 跟HK Journalist 跟中午抢饭的国大班同学们一样快
#include#include #include #include #include using namespace std;typedef long long ll;#define enter putchar('\n')#define space putchar(' ')template void read(T &x){ char c; bool op = 0; while(c = getchar(), c > '9' || c < '0') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x;}template void write(T x){ if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10);}const int W = 105, N = 100005, M = 1000005, INF = 0x3f3f3f3f;const int dx[] = {0, 0, 1, -1};const int dy[] = {1, -1, 0, 0};int n, m, mp[W][W], src, des;int ecnt = 1, adj[N], cur[N], dis[N], go[M], nxt[M], cap[M];#define id(x, y) (((x) - 1) * m + (y))void ADD(int u, int v, int _cap){ go[++ecnt] = v; nxt[ecnt] = adj[u]; adj[u] = ecnt; cap[ecnt] = _cap;}void add(int u, int v, int _cap){ ADD(u, v, _cap); ADD(v, u, 0);}bool bfs(){ static int que[N], qr; for(int i = 1; i <= des; i++) dis[i] = -1, cur[i] = adj[i]; dis[src] = 0, que[qr = 1] = src; for(int ql = 1; ql <= qr; ql++){ int u = que[ql]; for(int e = adj[u], v; e; e = nxt[e]) if(cap[e] && dis[v = go[e]] == -1){ dis[v] = dis[u] + 1, que[++qr] = v; if(v == des) return 1; } } return 0;}int dfs(int u, int flow){ if(u == des) return flow; int ret = 0, delta; for(int &e = cur[u], v; e; e = nxt[e]) if(cap[e] && dis[v = go[e]] == dis[u] + 1){ delta = dfs(v, min(flow - ret, cap[e])); if(delta){ cap[e] -= delta; cap[e ^ 1] += delta; ret += delta; if(ret == delta) return ret; } } dis[u] = -1; return ret;}int maxflow(){ int ret = 0; while(bfs()){ int flow; do{ ret += (flow = dfs(src, INF)); }while(flow); } return ret;}bool legal(int i, int j){ return i > 0 && j > 0 && i <= n && j <= m && mp[i][j] != 1;}int main(){ read(n), read(m), src = n * m + 1, des = src + 1; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) read(mp[i][j]); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){ if(mp[i][j] == 1) add(src, id(i, j), INF); else if(mp[i][j] == 2) add(id(i, j), des, INF); if(mp[i][j] != 2) for(int k = 0, x, y; k < 4; k++) if(legal(x = i + dx[k], y = j + dy[k])) add(id(i, j), id(x, y), 1); } write(maxflow()), enter; return 0;}