最大独立集个数模板 + 最大团计数模板

并没有看懂求最大团个数的算法原理???,已知看到最好的解释最大团blog

POJ 2989

最大团计数模板

  • R集合是 最大团已经加入的点
  • P集合是 可能加入的点,且与R集合所有的点存在边(????)
  • 还是不太明白X集合的作用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cstring>

using namespace std;

const int maxn = 135;

bool mp[maxn][maxn];
int r[maxn][maxn],p[maxn][maxn],x[maxn][maxn];
int n,m,ans;

void dfs(int d,int an,int sn,int nn) {
    if (!sn && !nn) ++ans;
    int u = p[d][0];
    for (int i=0; i<sn; ++i) {
        int v = p[d][i];
        if (mp[u][v]) continue;
        for (int j=0; j<an; ++j)
            r[d+1][j] = r[d][j];
        r[d+1][an] = v;
        int tsn=0,tnn=0;
        for (int j=0; j<sn; ++j) if(mp[v][p[d][j]]) p[d+1][tsn++] = p[d][j];
        for (int j=0; j<nn; ++j) if(mp[v][x[d][j]]) x[d+1][tnn++] = x[d][j];
        dfs(d+1,an+1,tsn,tnn);
        p[d][i] = 0;
        x[d][nn++] = v;

        if (ans > 1000) return;
    }
}

int work () {
    ans = 0;
    for (int i=0; i<n; ++i) p[1][i] = i+1;
    dfs(1,0,n,0);
    return ans;
}

int main() {
    freopen("1.in","r",stdin);
    while (scanf("%d%d",&n,&m) != EOF) {
        memset(mp,0,sizeof mp);
        for (int i=1; i<=m; ++i) {
            int u,v;
            scanf("%d%d",&u,&v);
            mp[u][v] = mp[v][u] = 1;
        }
        int temp = work();
        if (temp > 1000) printf("Too many maximal sets of friends.\n");
        else printf("%d\n",temp);
    }
    return 0;
}

但是做到一个 最大独立集POJ 1419的时候

  • 用到了结论: 最大独立集 = 补图的最大团
  • 于是我在此题转化成补图 套用 上面的 最大团模板 过了???
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int maxn = 135;

bool mp[maxn][maxn];
int r[maxn][maxn],p[maxn][maxn],x[maxn][maxn];
int n,m;
vector<int> ans;

void dfs(int d,int an,int sn,int nn) {
    if (!sn && !nn) {
        if (an > ans.size()) {
            ans.clear();
            for (int i=0; i<an; ++i)
                ans.push_back(r[d][i]);
        }
    }
    int u = p[d][0];
    for (int i=0; i<sn; ++i) {
        int v = p[d][i];
        if (mp[u][v]) continue;
        for (int j=0; j<an; ++j)
            r[d+1][j] = r[d][j];
        r[d+1][an] = v;
        int tsn=0,tnn=0;
        for (int j=0; j<sn; ++j) if(mp[v][p[d][j]]) p[d+1][tsn++] = p[d][j];
        for (int j=0; j<nn; ++j) if(mp[v][x[d][j]]) x[d+1][tnn++] = x[d][j];
        dfs(d+1,an+1,tsn,tnn);
        p[d][i] = 0;
        x[d][nn++] = v;
        //if (ans > 1000) return;
    }
}

void  work () {
    ans.clear();
    for (int i=0; i<n; ++i) p[1][i] = i+1;
    dfs(1,0,n,0);
}

int main() {
    freopen("1.in","r",stdin);
    int times; scanf("%d",&times);
    while (times--) {
        //cin >> n >> m;
        scanf("%d%d",&n,&m);
        memset(mp,0,sizeof mp);
        for (int i=1; i<=m; ++i) {
            int u,v;
            scanf("%d%d",&u,&v);
            mp[u][v] = mp[v][u] = 1;
        }
        for (int i=1; i<=n; ++i)
            for (int j=1; j<=n; ++j) {
                if(i == j) mp[i][j] = 0;
                else mp[i][j] ^= 1;
            }
        work();
        printf("%d\n",(int)ans.size());
        for (int i=0; i<ans.size(); ++i)
            printf("%d ",ans[i]);
        printf("\n");

    }
    return 0;
}

看到一遍优质Blog DFS直接求 最大独立集

  • 邻接表存图,但是该dfs函数并不是通过边去搜,而是 (类似遍历,但是是递归) 去访问下一个点(无论有无边),通过邻接表能够访问与该点连接的所有边
  • cur表示节点编号, cur>n遍历完所有的点 all[i]数组标记点i为黑色,num表示当前dfs进行中黑色点的个数
  • if(flag):表示周围的点都不是黑色点时
  • 精华:num + n-cur > ans.当flag==0或者flag==1dfs回溯回来时进行判断.
    1. num < ans但是剩下的未访问的点数n - cur大于ans - num 即n-cur > ans-num ,所以dfs仍有机会更新ans
    2. num > ans,黑色点数已经超过ans,剩下的点可以继续更新ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 1e5;
int n,m,tot,ans,len;
int head[150],all[150],point[150];
struct node { int v,next; } edge[maxn];

void add(int u,int v) {
    edge[tot].v = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

void dfs(int cur,int num) {
    if (cur > n) {
        //printf("num=%d ans=%d \n",num,ans);
        if (num > ans) {
            ans = num;
            len = 0;
            for (int i=1; i<=n; ++i)
                if (all[i]) {
                    point[len++] = i;
                }
        }
        return ;
    }
    bool flag = 1;
    for (int i=head[cur]; i!=-1; i=edge[i].next) {
        if (all[edge[i].v]) {
            flag = 0;
            break;
        }
    }
    if (flag) {
        all[cur] = 1;
        //printf("cur = %d num = %d ->  to = %d num = %d \n",cur,num,cur+1,num+1);
        dfs(cur+1,num+1);
        all[cur] = 0;
        //printf("all[%d]=0 -> ",cur);
    }
    if (num+(n-cur) > ans) {
        //printf("num= %d + n= %d - cur=%d > ans=%d \n",num,n,cur,ans);
        dfs(cur+1,num);
        //printf("out of end\n");
    }
}

void init() {
    ans = tot = 0;
    memset(head,-1,sizeof head);
    //memset();
}

int main() {
    freopen("1.in","r",stdin);
    int times; cin >> times;
    while (times--) {
        init();
        scanf("%d%d",&n,&m);
        for (int i=1; i<=m; ++i) {
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
        }
        dfs(1,0);
        printf("%d\n",ans);
        for (int i=0; i<len; ++i)
            printf("%d ",point[i]);
        printf("\n");
    }
    return 0;
}

算法
模板 遗留问题

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！