棋盘模型 + 动态加边

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<queue>

#define ll long long

#define M 51

#define N 500010

#define mmp make_pair

const int inf = 0x3e3e3e3e;

using namespace std;

int read()

{

	int nm = 0, f = 1;

	char c = getchar();

	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';

	return nm * f;

}

char S[M][M];

struct Note

{

	int ver, nxt, vi, vj, cap, flow;

}edge[N];

int head[N], cnt = 1, n, s, t, cost, ans;

bool vis[5010];

int dis[5050], sd[5050 * 30], sum[5050 * 30], noteans[5050], upup;

int tota, totb, notea[M][M], noteb[M][M], suma[M * M], sumb[M * M], nowa[M * M], nowb[M * M];

void push(int vi, int vj, int flo, int ver)

{

//	cout << vi << " " << vj << " " << ver << "\n";

	cnt++; edge[cnt].vi = vi, edge[cnt].ver = ver, edge[cnt].vj = vj, edge[cnt].nxt = head[vi], head[vi] = cnt, edge[cnt].cap = flo;

	cnt++; edge[cnt].vi = vj, edge[cnt].ver = -ver, edge[cnt].vj = vi, edge[cnt].nxt = head[vj], head[vj] = cnt;

}

bool spfa(int be, int ed)

{

	queue<int> q;

	for(int i = 0; i <= t; i++) vis[i] = 0, dis[i] = inf;

	dis[be] = 0, sum[s] = 0x3e3e3e3e;

	q.push(be);

	while(!q.empty())

	{

		int now = q.front();

		q.pop();

		vis[now] = false;

		for(int i = head[now]; i; i = edge[i].nxt)

		{

			int vj = edge[i].vj;

			if(edge[i].flow >= edge[i].cap) continue;

			if(dis[vj] > dis[now] + edge[i].ver)

			{

				dis[vj] = dis[now] + edge[i].ver;

				sd[vj] = i;

				sum[vj] = min(sum[now], edge[i].cap - edge[i].flow);

				if(!vis[vj])

				{

					vis[vj] = true;

					q.push(vj);

				}

			}

		}

	}

	if(dis[ed] == inf) return 0;

	ans += sum[ed];

	cost += sum[ed] * dis[ed];

	int u = ed, x;

	while(u != be)

	{

		x = sd[u];

		int vi = edge[x].vi, vj = edge[x].vj;

		if(vi == s && nowa[vj] + 1< suma[vj])

		{

			nowa[vj]++;

			push(s, vj, 1, nowa[vj]);

		}

		if(vj == t &&  nowb[vi - tota] + 1 < sumb[vi - tota])

		{

			nowb[vi - tota]++;

			push(vi, t, 1, nowb[vi - tota]);

		}

		edge[x].flow += sum[ed];

		edge[x ^ 1].flow -= sum[ed];

		u = edge[x].vi;

	}

	return true;

}

int main()

{

	n = read();

	for(int i = 1; i <= n; i++) scanf("%s", S[i] + 1);

	for(int i = 1; i <= n; i++)

	{

		for(int j = 1; j <= n; j++)

		{

			if(S[i][j] == '.') upup++;

		}

	}

	for(int i = 1; i <= n; i ++)

	{

		for(int j = 1; j <= n; j++)

		{

			if(j == 1 || (S[i][j - 1] == '#' && S[i][j] == '.')) tota++;

			if(S[i][j] == '#') continue;

			suma[tota]++, notea[i][j] = tota;

		}

	}

	for(int j = 1; j <= n; j++)

	{

		for(int i = 1; i <= n; i++)

		{

			if(i == 1 || (S[i - 1][j] == '#' && S[i][j] == '.')) totb++;

			if(S[i][j] == '#') continue;

			sumb[totb]++, noteb[i][j] = totb;

			push(notea[i][j], tota + noteb[i][j], 1, 0);

		}

	}

	s = tota + totb + 1, t = s + 1;

	for(int i = 1; i <= tota; i++) if(suma[i]) push(s, i, 1, 0);

	for(int i = 1; i <= totb; i++) if(sumb[i]) push(i + tota, t, 1, 0);

	for(int tim = 1; tim <= upup; tim++)

	{

		spfa(s, t);

		noteans[tim] = cost;

	}

	int t = read();

	while(t--)

	{

		int x = read();

		if(x > upup) puts("0");

		else cout << noteans[x] << "\n";

	}

	return 0;

}

/*

3

...

...

...

5

*/