题解：监狱囚犯交换问题

这段代码解决的是一个关于二分图匹配的问题，具体来说是要找到两个监狱之间最大的囚犯交换数量，同时确保没有危险对的囚犯被交换到同一监狱。问题可以转化为在一个二分图中找到最大的独立集，使得交换后的囚犯集合不包含任何危险对。

问题分析

两所监狱各有m名囚犯，存在r对危险关系，每对包含一名第一监狱的囚犯和一名第二监狱的囚犯。目标是交换两监狱各k名囚犯，使得k尽可能大且不违反任何危险关系。

代码详细解释

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXN 210

// 边结构
struct LEdge{
    int ed, next;
}edge[MAXN * MAXN];
int head[2 * MAXN], nEdge;

// 初始化图
void init(){
    nEdge = 0;
    memset(head, 0xff, sizeof(head));
}

// 添加边
void addEdge(int i, int j){
    edge[nEdge].ed = j;
    edge[nEdge].next = head[i];
    head[i] = nEdge++;
}

int f[MAXN][MAXN];  // DP数组，f[i][j]表示能否从原监狱选i人，从交换监狱选j人
int vis[MAXN][2];   // 标记节点是否被访问

int m, r;
int np, nq;  // 记录DFS中两种类型节点的数量

// DFS遍历图，计算连通块中两种类型节点的数量
void dfs(int cur, int flag){
    int i;
    if (!flag) np++;  // 类型0节点计数
    else nq++;        // 类型1节点计数
    vis[cur][flag] = 1;
    
    // 遍历所有邻接边
    for (i = head[2 * cur + flag]; i != -1; i = edge[i].next){
        if (vis[edge[i].ed / 2][1 - flag]) continue;
        dfs(edge[i].ed / 2, 1 - flag);
    }
}

// 动态规划更新可能的选择
void dp(int np, int nq){
    int j, k;
    // 逆序遍历，确保每个连通块只被考虑一次
    for (j = m / 2; j >= 0; j--){
        for (k = m / 2; k >= 0; k--){
            if (j - np >= 0 && k - nq >= 0){
                f[j][k] |= f[j - np][k - nq];  // 可以从之前的状态转移过来
            }
        }
    }
}

int main(){
    int i, j, k, T;
    scanf("%d", &T);  // 读取测试用例数量
    
    while(T--){
        init();  // 初始化图
        scanf("%d%d", &m, &r);  // 读取囚犯数量和危险对数量
        
        // 构建图：添加危险对的边
        for (k = 0; k < r; k++){
            scanf("%d%d", &i, &j);
            addEdge(2 * i, 2 * j + 1);      // 第一监狱的i不能和第二监狱的j在同一组
            addEdge(2 * j + 1, 2 * i);      // 双向边
        }
        
        // 初始化访问标记和DP数组
        memset(vis, 0, sizeof(vis));
        memset(f, 0, sizeof(f));
        f[0][0] = 1;  // 初始状态：不选任何囚犯
        
        // 遍历所有节点，处理每个连通块
        for (i = 1; i <= m; i++){
            if (!vis[i][0]){
                np = nq = 0;
                dfs(i, 0);  // 从类型0节点开始DFS
                dp(np, nq);  // 更新DP数组
            }
            if (!vis[i][1]){
                np = nq = 0;
                dfs(i, 1);  // 从类型1节点开始DFS
                dp(np, nq);  // 更新DP数组
            }
            if (f[m / 2][m / 2]) break;  // 如果已经找到最大可能的k，提前退出
        }
        
        // 查找最大的k，使得f[k][k]为真
        for (i = m / 2; i >= 0; i--)
            if (f[i][i]) break;
        printf("%d\n", i);  // 输出结果
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(T * m^2)，其中T是测试用例数量，m是囚犯数量。每个测试用例需要构建图、进行DFS分解和动态规划计算。
• 空间复杂度：O(m^2)，主要用于存储DP数组和图的邻接表。

这个算法通过将问题转化为图的连通块分析和动态规划，巧妙地解决了囚犯交换的最大匹配问题，确保了在满足所有约束条件的情况下找到最优解。