最大互斥$01$矩阵

#include <iostream>
using namespace std;
int judge[20][20];
int arr[1000][20];
int bestcolumn = 0; // record the best ans
int a[20], b[20];   // record the chosen column of A or B
int ansA[20], ansB[20];
void dfs(int column, int nowcoA, int nowcoB)
{
    if (20 - column + nowcoB + nowcoA < bestcolumn) // 如果就算把剩余的列全部选上都没有当前最大方案大的话，就没有必要再搜下去了
        return;
    if (column == 20 && nowcoA + nowcoB > bestcolumn && nowcoB != 0 && nowcoA != 0) // 如果这种选择方式集合列数更多，就判断是否满足不存在相同行的条件
    {
        int i, j, k, ok = 1;
        for (i = 0; i < 1000; i++)
        {
            int A = 0, B = 0;
            for (j = 0; j < 20; j++)
            {
                if (a[j] == 1 && arr[i][j] == 1) A = 1;
                if (b[j] == 1 && arr[i][j] == 1) B = 1;
            }
            if (A == 1 && B == 1) // 如果当前这两种选法中包含相同的行，就break
            {
                ok = 0;
                break;
            }
        }
        if (ok) // 两个集合中没有任何一列同时存在一行同时具有1，则说明当前选择方式可行
        {
            bestcolumn = nowcoB + nowcoA;  // 更新最大列数和
            for (int m = 0; m < 20; m++)  ansA[m] = a[m], ansB[m] = b[m];// 更新选择方案
        }
        return;
    }
    if (column == 20)  // 搜到终点直接返回
        return;
    int okB = 1, okA = 1;

    // ① 判断当前列是否可加到A中
    if (nowcoB != 0)  // 判断当前枚举的行和集合B是否存在某行同时有1，如果有，则当前行不能加到A中
    {
        for (int i = 0; i < 20; i++)
        {
            if (b[i] == 1 && judge[column][i] == 0)  // 有同时存在1的行
            {
                okA = 0;
                break;
            }
        }
    }
    if (okA)  // 如果当前列和集合B不存在同时有1的行，就直接加到A中
    {
        a[column] = 1; 
        dfs(column + 1, nowcoA + 1, nowcoB);
        a[column] = 0;
    }

    // ② 判断当前列是否可加到B中
    if (nowcoA != 0)  // 判断当前枚举的行和集合A是否存在某行同时有1，如果有，则当前行不能加到B中
        for (int i = 0; i < 20; i++)
            if (a[i] == 1 && judge[column][i] == 0)  // 有同时存在1的行
            {
                okB = 0;
                break;
            }
    if (okB)  // 如果当前列和集合A不存在同时有1的行，就直接加到B中
    {
        b[column] = 1; 
        dfs(column + 1, nowcoA, nowcoB + 1);
        b[column] = 0;
    }

    // ③ 当前行既不加到A中也不加到B中
    dfs(column + 1, nowcoA, nowcoB);  
}
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int i, j, k;
    for (i = 0; i < 1000; i++)
        for (j = 0; j < 20; j++)
            cin >> arr[i][j];

    // 将两列之间是否存在某行同时有1预处理出来，如果没有行同时有1就标记judge[i][j]=1
    for (i = 0; i < 20; i++)
        for (j = i + 1; j < 20; j++)
        {
            int ok = 0;
            for (k = 0; k < 1000; k++)
            {
                if (arr[k][i] == 1 && arr[k][j] == 1) // 如果这两列在第k行同时有1
                {
                    ok = 1;
                    break;
                }
            }
            if (!ok) judge[i][j] = judge[j][i] = 1;  // 标记这两列没有任意一行是同时有1的
        }
    dfs(0, 0, 0);
    for (i = 0; i < 20; i++)
        if (ansA[i]) cout << i << " ";

    cout << endl;
    for (i = 0; i < 20; i++)
        if (ansB[i]) cout << i;
    return 0;
}