专栏文章

最大团

__InRedBrother_QWQ_
算法·理论参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
2 份
快照标识符
@mlia9uag
此快照首次捕获于
2026/02/12 01:08
上周
此快照最后确认于
2026/02/19 01:17
16 小时前
查看原文

最大团

简介一下：给出一个 nn 个点 mm 条边的无向无边权图，求其中最大团的节点个数。
团的定义：∀u,v∈\forall u, v \in 该团，uu、vv 间一定有连边。
数据范围：n∈[1,35],m∈[1,(n−1)×n2]n \in [1, 35], m \in [1, \frac{(n - 1) \times n}{2}]。

大方向：状态压缩问题

几十几十的值域，只有三种潜台词：
  1. 搜索多写几层；
  2. DP 状态多开几维；
  3. 可以用一个二进制整数压缩状态。
搜索的方法，详见一哥们的代码：
一哥们的代码C
//若两个点在同一团中，则这两个点在其反图中无连边
#include<bits/stdc++.h>
#define int long long
namespace FastIO{
    template<typename T>inline void read(T &x){
        x=0;int f=1;char c=getchar();
        for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
        for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
    }
    template<typename T,typename...Args>
    inline void read(T &x,Args&...args){
        read(x);
        read(args...);
    }
    template<typename T>void print(T x){
        if(x<0)x=-x,putchar('-');
        if(x>9)print(x/10);
        putchar(x%10^48);
    }
}
using namespace FastIO;
using namespace std;
const int N=40;
int n,m,ans,now;
bool ing[N];
set<int>s[N];
void dfs(int u){
    if(u>n){
        ans=max(ans,now);
        return;
    }
    bool f=true;
    for(auto v:s[u]){
        if(ing[v]){
            f=false;
            break;
        }
    }
    if(f){
        now++;
        ing[u]=true;
        dfs(u+1);
        now--;
        ing[u]=false;
    }
    if(n+(now-u)>=ans){
        dfs(u+1);
    }
}
signed main(){
	read(n,m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            s[i].insert(j);
        }
    }
    for(int i=1;i<=m;i++){
        int u,v;
        read(u,v);
        s[v].erase(u);
    }
    dfs(1);
    print(ans);
}
这里考虑状压，不过 2352^{35} 超过了 10810^{8}，不能直接用以枚举，所以考虑状态压缩时，分成前一半的点 i∈[1,⌊n2⌋]i \in [1, \left \lfloor \frac{n}{2} \right \rfloor]和后一半的点 j∈[⌊n2⌋+1,n]j \in [\left \lfloor \frac{n}{2} \right \rfloor + 1, n]。这样，每次压缩的状态最多为 2182^{18}，更为方便处理。

左右分别处理团

有分就有和。将 nn 个点分开处理倒是好办，不过这要如何联系到答案的统计呢？
我们想到，一个大团一定可以看作两个小团，小团之间的每一个点又都有边相连。那么我们可以事先处理出分居左侧的所有点中的所有团、和分居右侧的所有点中的所有团，最后考虑合并统计答案。
找团，好办。枚举状态 II，检查 II 是否为团。
为此，我们要事先预处理所有分居左侧的点 ii，将点 ii 所有连出去的边的终点中，分居于左侧的终点压缩成一个整数，存放作为边集 Lef2iLef_{2^i}；所有分居右侧的点 jj 亦然，存放作为边集 Rit2jRit_{2^j} 。
实现C
	cin >> n, L = n / 2 + 1, R = n - L;
	cin >> m;
	for(int i = 1; i <= m; i ++) {
		cin >> a >> b;

		if(b <= L) Lef[1 << (a - 1)] |= (1 << (b - 1)), Lef[1 << (b - 1)] |= (1 << (a - 1));
		if(a > L) Rit[1 << (a - L - 1)] |= (1 << (b - L - 1)), Rit[1 << (b - L - 1)] |= (1 << (a - L - 1));
		if(a <= L && b > L) L_R[1 << (a - 1)] |= (1 << (b - L - 1));
	}
时间复杂度 O(m)O(m)。
这样，枚举位于左侧的点集 II，找到每一个 i∈Ii \in I，判断他的边集 Lef2iLef_{2^i} 是否严格包含 II 就行；枚举位于右侧的点集 JJ 亦然。
实现C
	for(int I = 1; I < (1 << L); I ++) {
		int dI = I, i, f = 1;
		while(dI) {
			i = dI - (dI & (dI - 1)), dI = (dI & (dI - 1));
//			cerr<<"Lef["<<i<<"]:"<<Lef[i]<<"; "<<I<<"\n";
			if((Lef[i] | I) ^ Lef[i]) {f = 0; break;}
		}

		if(f) canL[I] = true, can.emplace_back(I);
//		cerr<<I<<" "<<f<<"\n";
	}
	for(int J = 1; J < (1 << R); J ++) {
		int dJ = J, j, g = 1;
		while(dJ) {
			j = dJ - (dJ & (dJ - 1)), dJ = (dJ & (dJ - 1));
			if((Rit[j] | J) ^ Rit[j]) {g = 0; break;}
		}

		if(g) canR[J] = true;
	}
时间复杂度 O(2L×L)O(2^L \times L)。
关于我为什么不将边集存在 LefiLef_i 中，而要存在 Lef2iLef_{2^i} 中
原因很简单：当时我还不会 __builtin_ctz(i) + 1 这种手段，就只能每次取出一个 2i2^i，代表 ii 位置的状态为 11。
C
		int dI = I, i, f = 1;
		while(dI) {
			i = dI - (dI & (dI - 1)), dI = (dI & (dI - 1));
			if((Lef[i] | I) ^ Lef[i]) {f = 0; break;}
		}
所以为了方便调用，就选择这样存储的。实际上用空间复杂度换取代码整洁度与时间复杂度。

合并

此时，我们手握分别分居左侧与右侧的所有团，那么我们选择枚举左边的团再枚举右边的团两两配对……吗？恐怕过不去。
所以，引入另一个点集 L_R2iL\_R_{2^i}，表示分居左侧的点 ii 所有连出去的边的终点中，分居于右侧的终点压缩成的一个边集。
那么我们枚举分居左侧的每一个团 II，用它所含的每一个点的 L_R2iL\_R_{2^i} 值与起来求得一个分居右侧的点集 I1I_1，判断起是否为一个团，更新答案。
不过想到，如果 I1I_1 并非一个团，而它的某些子集是团，这样倒是也可以更新答案。所以还要再枚举 I1I_1 的子集。
实现C
	for(auto I : can) {
		int dI = I, i, J = (1 << R) - 1;
		while(dI) {
			i = dI - (dI & (dI - 1)), dI = (dI & (dI - 1));
			J = (J & L_R[i]);
		}

		int dJ = J;
		while(dJ) {
			if(true == canR[dJ]) ans = max(ans, num[I] + num[dJ]);
			dJ = (dJ - 1) & J;
		}
	}
时间复杂度 O(3L)O(3^L)。
总体来说，很悬但由于常数优秀，且测评机性能较好，最终过了。

总体实现

C
#include <bits/stdc++.h>
#define int long long
using namespace std;

int t = 1;

const int N = 35 + 5, M = 595 + 5, INF = 262144 + 10;
int n, L, R;
int m, a, b;
int Lef[INF], Rit[INF], L_R[INF];
bool canL[INF], canR[INF];
vector <int> can;

int num[INF];
void prepar() {
	for(int I = 0; I < INF; I ++) {
		int dI = I;
		while(dI) num[I] ++, dI = (dI & (dI - 1));
	}
	for(int i = 0; i <= 18; i ++) {
		Lef[1 << i] |= (1 << i), Rit[1 << i] |= (1 << i);
	}
}

int ans;

void solve() {
	cin >> n, L = n / 2 + 1, R = n - L;
	cin >> m;
	for(int i = 1; i <= m; i ++) {
		cin >> a >> b;

		if(b <= L) Lef[1 << (a - 1)] |= (1 << (b - 1)), Lef[1 << (b - 1)] |= (1 << (a - 1));
		if(a > L) Rit[1 << (a - L - 1)] |= (1 << (b - L - 1)), Rit[1 << (b - L - 1)] |= (1 << (a - L - 1));
		if(a <= L && b > L) L_R[1 << (a - 1)] |= (1 << (b - L - 1));
	}
//	for(int i=0;i<L;i++)cerr<<i<<"::"<<Lef[(1<<i)]<<"\n";
//	for(int j=0;j<R;j++)cerr<<j<<"::"<<Rit[(1<<j)]<<"\n";
//	for(int i=0;i<L;i++)cerr<<i<<"::"<<L_R[(1<<i)]<<"\n";

	for(int I = 1; I < (1 << L); I ++) {
		int dI = I, i, f = 1;
		while(dI) {
			i = dI - (dI & (dI - 1)), dI = (dI & (dI - 1));
//			cerr<<"Lef["<<i<<"]:"<<Lef[i]<<"; "<<I<<"\n";
			if((Lef[i] | I) ^ Lef[i]) {f = 0; break;}
		}

		if(f) canL[I] = true, can.emplace_back(I);
//		cerr<<I<<" "<<f<<"\n";
	}
	for(int J = 1; J < (1 << R); J ++) {
		int dJ = J, j, g = 1;
		while(dJ) {
			j = dJ - (dJ & (dJ - 1)), dJ = (dJ & (dJ - 1));
			if((Rit[j] | J) ^ Rit[j]) {g = 0; break;}
		}

		if(g) canR[J] = true;
	}

	for(auto I : can) {
		int dI = I, i, J = (1 << R) - 1;
		while(dI) {
			i = dI - (dI & (dI - 1)), dI = (dI & (dI - 1));
			J = (J & L_R[i]);
		}

		int dJ = J;
		while(dJ) {
			if(true == canR[dJ]) ans = max(ans, num[I] + num[dJ]);
			dJ = (dJ - 1) & J;
		}
	}

	cout << ans;
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	prepar();

//	cin >> t;
	while(t --) solve();
	return 0;
}

最后

其实本题主要是为了学习**“分成两半再合起来”**这个trick。
事后教练说本题有其他优化，不过被细心的同学证伪了。
（教练：诶，AI 几爷子改了一中午没发现这是错的嘞？）
所以不要依赖于 AI。

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...