BZOJ4930 棋盘 <费用流>

Posted on Symbols count in article: 1.2k Reading time ≈ 4 mins.

Problem

棋盘

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  512  MB\mathrm{Memory\;Limit:\;512\;MB}

Description

给定一个n×nn\times n的棋盘，棋盘上每个位置要么为空要么为障碍。定义棋盘上两个位置(x,y),(u,v)(x,y),(u,v)能互相攻击当前仅当满足以下两个条件：

  1. x=ux=u或y=vy=v
  2. 对于(x,y)(x,y)与(u,v)(u,v)之间的所有位置，均不是障碍。

现在有qq个询问，每个询问给定kik_i，要求从棋盘中选出kik_i个空位置来放棋子，问最少互相能攻击到的棋子对数是多少？

Input

第一行一个整数nn。
接下来输入一个n×nn\times n的字符矩阵，一个位置若为.，则表示这是一个空位置；若为#，则为障碍。
第n+2n+2行输入一个整数qq代表询问个数。
接下来qq行，每行一个整数kk，代表要放的棋子个数。

Output

输出共qq行，每行代表对应询问的最少的互相能攻击到的棋子对数。

Sample Input

1
2
3
4
5
6
4
..#.
####
..#.
..#.
1 7

Sample Output

1
2

HINT

n≤50n\le50, q≤104q\le10^4, k≤棋盘中空位置数量k\le棋盘中空位置数量

标签：费用流

Solution

“你见过拆点费用流吗？如果见过，那你见过拆边费用流吗？”

对于一块区域，若每个位置能互相攻击到，那么逐一放入棋子，第ii个放入的棋子会产生i−1i-1对新的攻击对关系。
注意到本题中这样的区域只可能是横着的或竖着的，这样我们可以预处理出若干个这样的横条和竖条，易知最多有n22×2\frac{n^2}{2}\times2个这样的区域。
按照以往的套路，我们将横条和竖条分开，这是因为对于一个格子，它同时在一个横条和一个竖条内。对于这样的每个横条，建一个点，并从源点连接到这个点。若这个横条中最多有kk个空位，那么流量最大为kk。然而每个单位流量的花费是不同的，于是建kk条边，第ii条边的费用为i−1i-1。对于每个竖条，建一个点，从这个点连到汇点，仍然建立kk条边，边权如法炮制。
之后对于每个点，找到其所在的横条和竖条，从横条的点连向竖条的点，流量11费用00。
跑费用流的时候，每次增广一定会新选一个格子，即流量增加11。记录下每增加一个格子的最小冲突对数即最小花费，即可预处理出每个kk的答案。跑完费用流后再回答询问即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
#define MAX_N 5000
#define MAX_M 20000
#define INF 0x3f3f3f3f
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, q, a, b, s, t, cnt, pr[MAX_N+5], cr[MAX_N+5], mxf, mic;
char mp[55][55]; int id[2][55][55], sz[2][MAX_N+5], ts[MAX_N+5], ans[MAX_N+5];
struct node {int v, c, w, nxt;} E[MAX_M+5];
void init() {s = 0, t = a+b+1, cnt = 0, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c, int w) {E[cnt] = (node){v, c, w, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c, int w) {insert(u, v, c, w), insert(v, u, 0, -w);}
bool SPFA() {
    queue <int> que; bool inq[MAX_N+5]; int d[MAX_N+5], cr[MAX_N+5];
    memset(inq, false, sizeof inq), memset(d, INF, sizeof d);
    d[s] = 0, que.push(s), inq[s] = true, memset(cr, -1, sizeof cr);
    while (!que.empty()) {
        int u = que.front(); que.pop(), inq[u] = false;
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c, w = E[i].w;
            if (c && d[u]+w < d[v]) {
                d[v] = d[u]+w, cr[v] = i;
                if (!inq[v]) que.push(v), inq[v] = true;
            }
        }
    }
    if (d[t] == INF) return false;	int flow = INF;
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) flow = min(flow, E[i].c);
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) E[i].c -= flow, E[i^1].c += flow;
    mxf += flow, mic += d[t];	return true;
}
int main() {
    read(n);
    for (int i = 1; i <= n; i++)
        scanf("%s", mp[i]+1), mp[i][0] = mp[0][i] = '#';
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) if (mp[i][j] == '.') {
            if (mp[i][j-1] == '#') id[0][i][j] = ++a, sz[0][a]++;
            else id[0][i][j] = id[0][i][j-1], sz[0][a]++;
        }
    for (int j = 1; j <= n; j++)
        for (int i = 1; i <= n; i++) if (mp[i][j] == '.') {
            if (mp[i-1][j] == '#') id[1][i][j] = ++b, sz[1][b]++;
            else id[1][i][j] = id[1][i-1][j], sz[1][b]++;
        }
    init();
    for (int i = 1; i <= a; i++)
        for (int j = 1; j <= sz[0][i]; j++)
            addedge(s, i, 1, j-1);
    for (int i = 1; i <= b; i++)
        for (int j = 1; j <= sz[1][i]; j++)
            addedge(i+a, t, 1, j-1);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
        if (mp[i][j] == '.') addedge(id[0][i][j], id[1][i][j]+a, 1, 0);
    read(q); while (SPFA()) ans[mxf] = mic;
    for (int k; q; q--) read(k), printf("%d\n", ans[k]);
    return 0;
}