这其实就是一道最小边覆盖的板儿题。
暴力连边，然后跑匈牙利（dinic），则答案就是总结点数-匹配数。
比如节点1和2,2和3匹配上了，那么就是1到2,2到3这两条路径连接到一块，相当于把节点3合并到这条路径上了。所以从路径数就是总结点数-连接次数。
然而我不知怎么想的写了个费用流，虽然正确性是对的，但是因为是一条条增广路找，就慢了很多……
#include #include #include #include #include #include #include #include #include #include using namespace std;#define enter puts("") #define space putchar(' ')#define Mem(a, x) memset(a, x, sizeof(a))#define In inlinetypedef long long ll;typedef double db;const int INF = 0x3f3f3f3f;const db eps = 1e-8;const int maxn = 55;const int maxN = 5e3 + 5;const int maxe = 1e7 + 5;inline ll read(){ ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) last = ch, ch = getchar(); while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); if(last == '-') ans = -ans; return ans;}inline void write(ll x){ if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0');}char s[maxn][maxn];int n, m, r, c, t;struct Edge{ int nxt, from, to, cap, cos;}e[maxe];int head[maxN], ecnt = -1;In void addEdge(int x, int y, int w, int c){ e[++ecnt] = (Edge){head[x], x, y, w, c}; head[x] = ecnt; e[++ecnt] = (Edge){head[y], y, x, 0, -c}; head[y] = ecnt;}bool in[maxN];int dis[maxN], pre[maxN], flow[maxN];In bool spfa(){ Mem(dis, 0x3f), Mem(in, 0); dis[0] = 0, flow[0] = INF; queue q; q.push(0); while(!q.empty()) { int now = q.front(); q.pop(); in[now] = 0; for(int i = head[now], v; ~i; i = e[i].nxt) { if(dis[v = e[i].to] > dis[now] + e[i].cos && e[i].cap > 0) { dis[v] = dis[now] + e[i].cos; pre[v] = i; flow[v] = min(flow[now], e[i].cap); if(!in[v]) q.push(v), in[v] = 1; } } } return dis[t] ^ INF;}int minCost = 0;In void update(){ int x = t; while(x) { int i = pre[x]; e[i].cap -= flow[t]; e[i ^ 1].cap += flow[t]; x = e[i].from; } minCost += flow[t] * dis[t];}In int MCMF(){ while(spfa()) update(); return minCost;}int dx[5], dy[5], DIR;In void init(){ if(r == c) { DIR = 2; dx[0] = r, dx[1] = r; dy[0] = r, dy[1] = -r; } else { DIR = 4; dx[0] = r, dx[1] = c, dx[2] = c, dx[3] = r; dy[0] = c, dy[1] = r, dy[2] = -r, dy[3] = -c; }}In int num(int x, int y, int z) {return (x - 1) * m + y + z * n * m;}In void build(int x, int y){ addEdge(0, num(x, y, 0), 1, 1); addEdge(num(x, y, 1), t, 1, 0); for(int i = 0; i < DIR; ++i) { int nx = x + dx[i], ny = y + dy[i]; if(nx > 0 && nx <= n && ny > 0 && ny <= m && s[nx][ny] == '.') addEdge(num(x, y, 0), num(nx, ny, 1), 1, 0); }}int main(){ //freopen("ha.in", "r", stdin); Mem(head, -1); n = read(), m = read(), r = read(), c = read(); t = n * m * 2 + 1; for(int i = 1; i <= n; ++i) scanf("%s", s[i] + 1); init(); int tot = 0; for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) if(s[i][j] == '.') build(i, j), ++tot; write(tot - MCMF()), enter; return 0;}