最大团

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

Posted on

一眼以为是状压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;

最大团

HDU 3585 maximum shortest distance

Posted on

淦啊……我之前自以为入门的最大团DP优化板子是错的,我说怎么和极大团计数差别这么多,那个原先的根本就是一个被谁自创的dfs+dp优化算法,速度平均慢一倍!!!

说句别的,终于刷完这套……给出链接
最大团与稳定婚姻专题

题意:
要你找出一个数量不小于 k 的最大团,使得最大团中的最短距离最大。

思路:
二分距离+最大团判定

老实说我一开始没想到,但看到这个思路之后就是豁然开朗,感觉二分的思路都是这样的……
然后疯狂TLE……不知道为什么,查了一下,最大团板子太慢了……原来学得是民间算法!!

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

#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)--)
#define fill(ary, num) memset(ary, (num), sizeof(ary))

using namespace std;

typedef pair<int, int> pii;
const int maxn = 55;

int n, k, ans;
pii point[maxn];
int some[maxn][maxn], dis[maxn][maxn];
int len[maxn * maxn], alimit;

inline int two(int x) { return x * x; }

int calc(int a, int b)
{
    return two(point[a].first - point[b].first) + two(point[a].second - point[b].second);
}

bool dfs(int deep, int sn, int an)
{
    if (an >= k)
        return true;
    if (sn + an < k)
        return false;
    int u = some[deep][1];
    range(i, 1, sn)
    {
        int v = some[deep][i];
        if (dis[u][v] >= alimit)
            continue;
        int tsn = 0;
        range(j, 1, sn) if (dis[v][some[deep][j]] >= alimit) some[deep + 1][++tsn] = some[deep][j];
        if (dfs(deep + 1, tsn, an + 1))
            return true;
        some[deep][i] = 0;
    }
    return false;
}

bool check(double limit)
{
    range(i, 1, n) some[1][i] = i;
    alimit = limit;
    return dfs(1, n, 0);
}

int main()
{
    while (scanf("%d %d", &n, &k) != EOF) {
        range(i, 1, n) scanf("%d %d", &point[i].first, &point[i].second);
        int num = 0;
        range(i, 1, n) range(j, i + 1, n)
        {
            dis[i][j] = dis[j][i] = calc(i, j);
            len[num++] = dis[i][j];
        }
        sort(len, len + num);
        int l = 0, r = num - 1, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (check(len[mid]))
                l = mid + 1;
            else
                r = mid - 1;
        }
        printf("%.2f\n", sqrt(len[l - 1]));
    }
    return 0;
}
最大团

POJ 2989 All Friends

Posted on

最大团问题之极大团计数。

啊呀啊呀,基本都会是板子题啦……
但是尽管是板子题,上次ccpc网络赛卡我的题,我当时要是有个最大团的板子,就可以直接过了……

极大团计数和最大团不大一样,这里有wiki上的伪代码

BronKerbosch(All, Some, None):
if Some and None are both empty:
report All as a maximal clique //所有点已选完,且没有不能选的点,累加答案
for each vertex v in Some: //枚举Some中的每一个元素
BronKerbosch1(All ⋃ {v}, Some ⋂ N(v), None ⋂ N(v))
//将v加入All,显然只有与v为朋友的人才能作为备选,None中也只有与v为朋友的才会对接下来造成影响
Some := Some - {v} //已经搜过,在Some中删除,加入None
None := None ⋃ {v}

其实就是一个优化过的回溯算法……最大团是NP问题,没办法,过几天会去学一下随机化吧。

题意:
极大团计数裸题,给你\( n \)个点,\( m\)条边,问你极大团数量。

思路:
具体看上面的伪代码。

值得注意的是,使用板子的时候格外要注意,边界外的邻接矩阵不能设置为 true ,不然会出错。不具体解释。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

#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)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int maxn = 130;

int ans;
bool g[maxn][maxn];
int some[maxn][maxn], none[maxn][maxn];
int all[maxn][maxn];

void dfs(int cur, int sz, int sn, int nn)
{
    if (!sn && !nn)
        ans++;
    if (ans > 1000)
        return;
    int key = some[cur][1];
    range(i, 1, sn)
    {
        int v = some[cur][i], tsn = 0, tnn = 0;
        if (g[key][v])
            continue;
        range(j, 1, sz) all[cur + 1][j] = all[cur][j];
        all[cur + 1][sz + 1] = v;
        range(j, 1, sn) if (g[v][some[cur][j]]) some[cur + 1][++tsn] = some[cur][j];
        range(j, 1, nn) if (g[v][none[cur][j]]) none[cur + 1][++tnn] = none[cur][j];
        dfs(cur + 1, sz + 1, tsn, tnn);
        some[cur][i] = 0, none[cur][++nn] = v;
    }
}

int main()
{
    int u, v, n, m;
    while (scanf("%d %d", &n, &m) != EOF) {
        fill(g, false), ans = 0;
        while (m--) {
            scanf("%d %d", &u, &v);
            g[u][v] = g[v][u] = true;
        }
        range(i, 1, n) some[1][i] = i;
        dfs(1, 0, n, 0);
        if (ans > 1000)
            puts("Too many maximal sets of friends.");
        else
            printf("%d\n", ans);
    }
    return 0;
}
最大团

最大团Bron–Kerbosch算法入门

Posted on

听了Yasola瞎逼逼打算去搞一下那些很混乱的东西。
首先就是这个最大团问题

建议先点开看看上面的百度百科链接。虽然东西很多,我也只是浏览了一下

瞎逼逼与个人理解

首先必须强调的是最大团是一个NP-Hard问题,目前并没有一个合适的在多项式时间内完美求得正解的算法。

而Bron–Kerbosch算法,名字好像是非常吊,其实就是各种优化过的搜索算法。
学习博客点这里

简单说一下个人理解。

Bron–Kerbosch算法基于基本搜索,但优化之处很多,优化有如下

  1. 比较常见的指定顺序搜索,避免重复
  2. 对于当前深度 dep , 如果剩余点数与之相加都不能更新 ans ,就剪枝
  3. dp 优化,用dp记录之前搜索得到的最大团数量,如无法更新ans,剪枝。

下面有两个入门 板子

HDU 1530 Maximum Clique

题意:
最大团的裸题。给你邻接矩阵,让你求最大团的点数。

思路:
套一套模板就行啦……

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

#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)--)
//#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int maxn = 55;

int n, ans;
int g[maxn][maxn], dp[maxn];
int vex[maxn];

bool isClique(const int& sz, const int& end)
{
    range(i, 1, sz) if (!g[vex[i]][end]) return false;
    return true;
}

void dfs(int dep, int cur)
{
    if (dep + n - cur + 1 <= ans || dep + dp[cur] <= ans)
        return;
    range(i, cur, n) if (isClique(dep, i))
    {
        vex[dep + 1] = i;
        dfs(dep + 1, i + 1);
    }
    ans = max(dep, ans);
}

int main()
{
    while (~scanf("%d", &n) && n) {
        range(i, 1, n) range(j, 1, n) scanf("%d", &g[i][j]);
        fill(dp, dp + n + 1, 0), dp[n] = 1, ans = 0;
        rrange(i, 1, n - 1)
        {
            vex[1] = i;
            dfs(1, i + 1);
            dp[i] = ans;
        }
        printf("%d\n", dp[1]);
    }
    return 0;
}

POJ 1419 Graph Coloring

题意:
给你一些边,让你求最大独立集。

思路:
无向图的最大独立集 = 补图的最大团。
因此建立补图,跑一遍即可。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

#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)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int maxn = 105;

int n, m, ans;
int g[maxn][maxn], dp[maxn];
int vex[maxn], avex[maxn];

bool isClique(const int& sz, const int& end)
{
    range(i, 1, sz) if (!g[vex[i]][end]) return false;
    return true;
}

void dfs(int dep, int cur)
{
    if (dep + n - cur + 1 <= ans || dep + dp[cur] <= ans)
        return;
    range(i, cur, n) if (isClique(dep, i))
    {
        vex[dep + 1] = i;
        dfs(dep + 1, i + 1);
    }
    if (ans < dep) {
        ans = dep;
        memcpy(avex, vex, sizeof vex);
    }
}

int main()
{
    int T, u, v;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        range(i, 1, n) range(j, 1, n) g[i][j] = 1;
        while (m--) {
            scanf("%d %d", &u, &v);
            g[u][v] = g[v][u] = 0;
        }
        fill(dp, 0), dp[n] = 1, ans = 0;
        rrange(i, 1, n - 1)
        {
            vex[1] = i;
            dfs(1, i + 1);
            dp[i] = ans;
        }
        printf("%d\n", dp[1]);
        range(i, 1, ans) printf("%d%c", avex[i], " \n"[i == ans]);
    }
    return 0;
}