算法1

最大独立集裸题

时间复杂度

参考文献

C++ 代码

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

const int N = 40, P = N * N, E = P * 4 * 2, INF = 0x3f3f3f3f;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int g[N][N], id[N][N];
int sum;
int h[P], e[E], ne[E], f[E], idx;
int q[P], hh, tt;
int d[P], cur[P];
int n, m, S, T;

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx ++;
    e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx ++;
} 

bool bfs()
{
    memset(d, -1, sizeof d);
    hh = tt = 0;
    d[S] = 0, cur[S] = h[S], q[0] = S;
    while(hh <= tt)
    {
        int t = q[hh ++ ];
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1 && f[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                if(j == T) return true;
                q[ ++ tt ] = j;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        int j = e[i];
        cur[u] = i;
        if(d[j] == d[u] + 1 && f[i])
        {
            int r = find(j, min(f[i], limit - flow));
            if(!r) d[j] = -1;
            flow += r, f[i] -= r, f[i ^ 1] += r;
        }
    }
    return flow;
}

int dinic()
{
    int res = 0;
    while(bfs()) res += find(S, INF);
    return res;
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
        {
            scanf("%d", &g[i][j]);
            sum += g[i][j];
        }
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
            id[i][j] = i * m + j;
    memset(h, -1, sizeof h);
    S = P - 1, T = P - 2;
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
            if((i + j) & 1)
            {
                for(int u = 0; u < 4; ++ u)
                {
                    int ui = i + dx[u], uj = j + dy[u];
                    if(ui >= 0 && ui < n && uj >= 0 && uj < m) 
                        add(id[i][j], id[ui][uj], INF);
                }
            }
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
            if((i + j) & 1)
                add(S, id[i][j], g[i][j]);
            else add(id[i][j], T, g[i][j]);
    printf("%d", sum - dinic());
    return 0;
}