题目分析

题意简述

本题包含 $t\_$ 组测试用例。对于每组测试用例，给定 $k$ 个三维布局（每个布局尺寸为 $m \times n$），以及别墅的高度 $h$ 和宽度 $w$。需要判断在每个布局中，是否能放置一个尺寸为 $h \times w$ 的别墅。若能直接放置，记为一种可行方案；若不能直接放置，但去掉某个特定字符后可以放置，则通过特定的网络流算法来计算额外的可行方案数。最终输出每组测试用例中总的可行方案数 $cnt$。

输入

• 第一行输入测试用例的组数 $t\_$。
• 对于每组测试用例：
  • 首先输入 $k$, $m$, $n$, $h$, $w$，分别表示布局数量、布局的高度、布局的宽度、别墅的高度、别墅的宽度。
  • 接着输入 $k$ 个布局，每个布局由 $m$ 行、每行 $n$ 个字符组成，字符 '0' 表示空地，其他大写字母表示不同类型的元素 。

输出

对于每组测试用例，输出一个整数 $cnt$，表示能够放置别墅的总方案数。

解题思路

初始化操作

通过 init 函数对全局变量进行初始化：

• 将二维数组 graph 所有元素置为 $0$，用于后续构建网络流图。
• 初始化计数器 $cnt$ 为 $0$，记录可行方案数；设置 $M = 26$ 表示字符类型数量（假设为 26 种大写字母），$N = 1$ 用于标记图中的节点编号。
• 将布尔数组 $s$ 和 $t$ 所有元素置为 false，表示对应节点可用。

判断布局可行性

1. 直接可行性判断：遍历每个布局，对于每个可能的 $h \times w$ 子区域，统计其中不同字符的数量。使用 type 函数判断子区域内字符情况：
   • 若子区域内无字符（全为 '0'）或只有一种字符，则可以直接放置别墅，将 $ZF$ 标记为 true，并结束当前布局的判断。
   • 若子区域内存在多种字符，则不能直接放置别墅，继续后续判断。
2. 通过去掉字符实现可行性判断：若不能直接放置别墅，检查去掉某个字符后是否可行。若可行，将该字符对应的节点与图中节点 $N$ 之间连边（graph[N][tp] = 1），并标记 $KF$ 为 true，同时将节点编号 $N$ 自增。

网络流算法求解

使用 pushflow 函数实现类似最大流的 push - relabel 算法：

1. BFS 寻找增广路径：使用队列 bfs 进行广度优先搜索，寻找从源点（标记为 $S$ 端的可用节点）到汇点（标记为 $T$ 端的可用节点）的增广路径。
2. 更新网络流图：若找到增广路径，通过调整路径上的边权（graph 数组）来更新网络流图，同时标记路径上经过的节点为已使用（更新 $s$ 和 $t$ 数组）。
3. 重复寻找增广路径：不断重复执行 pushflow 函数，直到无法找到增广路径为止。每次成功找到并更新路径，方案数 $cnt$ 增加 $1$。

结果输出

最终输出每组测试用例中总的可行方案数 $cnt$。

代码实现

#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;
const int SSS = 2147483647;
const int TTT = -2147483648;
bool s[101] = {false}, t[101] = {false};//false表示可用
int k,m,n,h,w;//k从1開始，m,n,h,w從洞開始
int layout[100][100][100];
int graph[100][100];
int cnt;
int M,N;

void init(){//所有初始化
    for(int i = 0; i < 100; i++){
        for(int j = 0; j < 100; j++){
            graph[i][j] = 0;
        }
    }
    cnt = 0;
    M = 26;
    N = 1;
    for(int i = 0; i < 101; i++){
        s[i] = t[i] = 0;
    }
}

int type(int *state){
    //返回状態码。0表示不用去掉就可以建，-1表示无论去掉谁都不行，正数代表可以去掉符合条件的编号
    int nonzero = -1;
    for(int i = 1; i <= 26; i++){
        if(state[i]>0 && nonzero!=-1) return -1;
        else if(state[i]>0){
            nonzero = i;
        }
    }
    if(nonzero==-1) return 0;
    return nonzero;
}

bool pushflow(){
    //如果push不了，返回false
    queue<int> bfs;
    bool getT = false;
    int noT;
    int S[101] = {0}, T[101] = {0};
    for(int i = 1; i < N; i++){
        if(!s[i]){
            S[i] = SSS;
            bfs.push(i);
        }
    }
    while(!bfs.empty()){
        int cur = bfs.front();
        bfs.pop();
        if(cur > 0){
            //是s这边的点
            for(int j = 1; j <= M; j++){
                if(graph[cur][j] == 1 && T[j] == 0){
                    bfs.push(-j);
                    T[j] = cur;
                }
            }
        }
        else{
            //是t这边的点
            int j = -cur;
            if(!t[j]){
                getT = true;
                noT = cur;
                break;
            }
            for(int i = 1; i < N; i++){
                if(graph[i][j] == -1 && S[i] == 0){
                    bfs.push(i);
                    S[i] = cur;
                }
            }
        }
    }
    if(!getT) return false;
    t[-noT] = true;
    int TtoS = 1;
    while(1){
        if(TtoS){
            //push路径当前从S端到T端
            int noS = T[-noT];
            graph[noS][-noT] = -1;
            noT = noS;
        }
        else{
            //从T端到S端
            int noS = S[noT];
            if(noS == SSS){
                s[noT] = true;
                break;
            }
            graph[noT][-noS] = 1;
            noT = noS;
        }
        TtoS = 1 - TtoS;
    }
    return true;
}

int main() {
    int t_;
    scanf("%d", &t_);
    for(int ii = 0; ii < t_; ii++){
        init();
        scanf("%d%d%d%d%d", &k,&m,&n,&h,&w);
        for(int i = 1; i <= k; i++){
            for(int j = 0; j < m; j++){
                char str[100];
                scanf("%s", str);
                for(int q = 0; q < n; q++){
                    char tr = str[q];
                    if(tr == '0') layout[i][j][q] = 0;
                    else layout[i][j][q] = tr-'A'+1;
                }
            }
        }
        if(h>m || w>n){
            printf("0\n");
            continue;
        }
        for(int i = 1; i <= k; i++){
            for(int z = 1; z <= 26; z++) graph[N][z] = 0;//清除上一个循环可能遗留的无效的1
            bool ZF = 0, KF = 0;//ZF: 是否可以直接建别墅 KF: 是否可以昆掉某个字呣建别墅
            int bfh[100][27] = {0};
            for(int j = 0; j < n; j++){
                for(int q = 0; q < h; q++){
                    bfh[j][layout[i][q][j]]++;
                }
            }
            for(int q = 0; q <= m-h; q++){
                int tmp[27] = {0};
                for(int j = 0; j < w; j++){
                    for(int z = 1; z <= 26; z++){
                        tmp[z] += bfh[j][z];
                    }
                }
                for(int j = 0; j <= n-w; j++){
                    int tp = type(tmp);
                    if(!tp) {
                        ZF = 1;
                        goto done;
                    }
                    if(tp>0){
                        KF = 1;
                        graph[N][tp] = 1;
                    }
                    if(j==n-w) break;
                    for(int z = 1; z <= 26; z++){
                        tmp[z] += (bfh[j+w][z] - bfh[j][z]);
                    }
                }
                if(q==m-h) break;
                for(int j = 0; j < n; j++){
                    bfh[j][layout[i][q+h][j]]++;
                    bfh[j][layout[i][q][j]]--;
                }
            }
            done:
            if(ZF) cnt++;
            else if(KF) N++;
        }
        while(pushflow()){
            cnt++;
        }
        printf("%d\n", cnt);
    }
    return 0;
}

代码说明

1. 全局变量定义：
   • 定义常量 SSS 和 TTT 分别表示极大值和极小值。
   • 布尔数组 s 和 t 用于标记节点是否可用。
   • 变量 $k$, $m$, $n$, $h$, $w$ 存储输入的布局相关参数。
   • 三维数组 layout 存储所有布局信息，二维数组 graph 用于构建网络流图。
   • 变量 $cnt$ 记录可行方案数，$M$ 和 $N$ 用于辅助网络流图构建和节点编号。
2. init 函数：完成对 graph 数组、计数器 $cnt$、变量 $M$ 和 $N$ 以及布尔数组 $s$ 和 $t$ 的初始化。
3. type 函数：根据传入的状态数组 state，判断子区域内字符情况并返回相应状态码。
4. pushflow 函数：实现网络流算法中的 push - relabel 过程，通过 BFS 寻找增广路径并更新网络流图。
5. main 函数：
   • 读取测试用例组数 $t\_$。
   • 对于每组测试用例，调用 init 函数初始化，读取布局相关参数和布局信息。
   • 判断别墅尺寸是否合法，若不合法直接输出 $0$ 并继续下一组测试用例。
   • 遍历每个布局，判断是否能直接放置别墅或通过去掉字符放置别墅，并构建网络流图。
   • 不断调用 pushflow 函数更新网络流图，直到无法找到增广路径，最终输出可行方案数 $cnt$。