算法1

DAG的最小重复路径覆盖

时间复杂度

参考文献

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 30;
int n, m;
char s[N][N];
bool g[410][410];
bool st[410];
int id[N][N];
int cnt;
int match[410];

int get(int i, int j)
{
    return id[i][j];
}

bool find(int x)
{
    for(int i = 1; i <= cnt; ++ i)
        if(g[x][i] && !st[i])
        {
            st[i] = true;
            int t = match[i];
            if(!t || find(t))
            {
                match[i] = x;
                return true;
            }
        }
    return false;
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; ++ i) scanf("%s", &s[i]);

    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
            if(s[i][j] == '1')
                id[i][j] = ++ cnt;

    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
            if(s[i][j] == '1')
            {
                if(i < n - 1 && s[i + 1][j] == '1') g[get(i, j)][get(i + 1, j)] = 1;
                if(j < m - 1 && s[i][j + 1] == '1') g[get(i, j)][get(i, j + 1)] = 1;
            }

    for(int k = 1; k <= cnt; ++ k)
        for(int i = 1; i <= cnt; ++ i)
            for(int j = 1; j <= cnt; ++ j)
                g[i][j] |= g[i][k] & g[k][j];

    int res = 0;
    for(int i = 1; i <= cnt; ++ i)
    {
        memset(st, 0, sizeof st);
        if(find(i)) res ++;
    }
    printf("%d", cnt - res);
    return 0;
}