HDU 5556 Land of Farms 附最大团最终模板

一眼以为是状压DP……
但是仔细读题的话，会有一个致命条件是状压无法解决的。

偷看了一下薛昊的博客，回去路上还跟我说二分图不可能建出来，结果到头来却用HK写这题。

题意：
给你一张图，是矩阵的形式，在满足条件的情况下你要选择尽可能多的格子。

其条件如下

• 如果选中一个格子，这个格子是数字，则相同数字的格子立刻被选中。
• 每个被选中的格子不允许其四个相邻的格子中 存在被选中且与其不同的格子

思路：
实际上这道题的确很想状压，如果把题目中的第一个条件改成，与其选中格子联通且数字相同的格子立马被选中的话，状压可解。但事实并非如此。

其实可以把所有是数字且相同的格子作为一个点，每个 . 也作为一个点，再将其与四周连边，按题意来的话，略加思考，其实就是个最大独立集的裸题。
但是关键还是需要转化出来啊……

坑点，答案最小为 1 。

AC Code

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 12;
const int maxv = maxn * maxn;

char mat[maxn][maxn];
int row, col;
int im[maxn][maxn];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };
bool g[maxv][maxv];
int ans;

inline bool judgeIn(int x, int y) { return x >= 0 && x < row && y >= 0 && y < col; }

void init()
{
    memset(im, 0, sizeof im);
    memset(g, true, sizeof g);
    ans = 1;
}

int createGraph()
{
    int cnt = 0;
    map<char, int> mp;
    each(i, row) each(j, col) if (im[i][j] == 0)
    {
        if (mat[i][j] == '.')
            im[i][j] = ++cnt;
        else {
            if (mp.find(mat[i][j]) == mp.end())
                mp[mat[i][j]] = ++cnt;
            im[i][j] = mp[mat[i][j]];
        }
        g[cnt][cnt] = false;
    }
    each(x, row) each(y, col)
    {
        int u = im[x][y], v;
        each(i, 4)
        {
            int xx = x + dx[i], yy = y + dy[i];
            if (judgeIn(xx, yy) && u != (v = im[xx][yy]))
                g[u][v] = g[v][u] = false;
        }
    }
    return cnt;
}

int vex[maxv], dp[maxv];
int stk[maxv][maxv];

void dfs(int n, int sz, int dep)
{
    if (sz == 0) {
        ans = max(ans, dep);
        return;
    }
    each(i, sz)
    {
        int u = stk[dep][i];
        if (dep + dp[u] <= ans || dep + sz - i <= ans)
            return;
        vex[dep] = u;
        int cnt = 0;
        range(j, i + 1, sz - 1)
        {
            int v = stk[dep][j];
            if (g[u][v])
                stk[dep + 1][cnt++] = v;
        }
        dfs(n, cnt, dep + 1);
    }
}

int maxClique(int n)
{
    memset(dp, 0, sizeof dp);
    dp[n] = 1;
    rrange(i, 1, n - 1)
    {
        int sz = 0;
        range(j, i + 1, n) if (g[i][j]) stk[1][sz++] = j;
        vex[0] = i;
        dfs(n, sz, 1);
        dp[i] = ans;
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d %d", &row, &col);
        each(i, row) scanf("%s", mat[i]);
        init();
        int n = createGraph();
        printf("Case #%d: %d\n", cas, maxClique(n));
    }
    return 0;
}

模板：
这是最大团的模板，极大团计数的点 这个
因为觉得极大团计数并没有找到最优的写法，至少还有一个优化没学就先不放了。

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxv = 110;

struct MC {
    bool g[maxv][maxv];
    int stk[maxv][maxv], dp[maxv];
    int vex[maxv], mcv[maxv];
    int n, mc;

    void init(int _n)
    {
        n = _n;
        memset(dp, 0, sizeof dp);
        //建图
    }

    void dfs(int sz, int dep)
    {
        if (sz == 0) {
            if (dep > mc) {
                mc = dep;
                each(i, mc) mcv[i] = vex[i];
            }
            return;
        }
        each(i, sz)
        {
            int u = stk[dep][i];
            if (dep + dp[u] <= mc || dep + sz - i <= mc)
                return;
            vex[dep] = u;
            int cnt = 0;
            range(j, i + 1, sz - 1)
            {
                int v = stk[dep][j];
                if (g[u][v])
                    stk[dep + 1][cnt++] = v;
            }
            dfs(cnt, dep + 1);
        }
    }

    int maxClique()
    {
        dp[n] = 1;
        rrange(i, 1, n - 1)
        {
            int sz = 0;
            range(j, i + 1, n) if (g[i][j]) stk[1][sz++] = j;
            vex[0] = i;
            dfs(sz, 1);
            dp[i] = mc;
        }
        return mc;
    }

} mc;