最大团
一张图的最大团被定义为它的一个极大的完全子图。
对于任意一张图，我们都有如下结论：其最大团就是其补图的最大独立集。读者自证不难。
于是乎，只要一张图的补图为二分图，我们就可以轻松求出它的最大团。
P2764
抽象一下题意，我们发现我们需要连一条边使得最大团的大小加一。
在补图中，连边会变为删边，又因为 \(最大团 = 补图最大独立集 = 补图总点数-最小点覆盖=补图总点数-最大匹配\)，所以要让最大团更大，最大匹配应当更小。
于是，我们暴力地枚举删哪一条匹配，然后暴力地检验最大匹配是否变少即可。
时间复杂度最坏可以达到 \(O(n^5)\)，显然无法通过，但可以获得 \(60 pts\) 的高分。正解也许会出现在第 93 期中。
code
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n,m;
int idx,ans;
int match[N],match2[N],vis[N],color[N];
vector<int> G[N],T[N];
vector<pair<int,int> > Ans;
void fillit(int cur,int c){
color[cur]=c;
for(int i:G[cur])
if(!color[i])
fillit(i,3-c);
}
bool hungary(int* mm,int cur,int pre,int nxt){
if(vis[cur]==idx){
return 0;
}
vis[cur]=idx;
for(int i:T[cur]){
if(cur==pre&&i==nxt)
continue;
if(!mm[i]||hungary(mm,mm[i],pre,nxt)){
mm[i]=cur;
return 1;
}
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=n;i++)
if(!color[i])
fillit(i,1);
for(int i=1;i<=n;i++){
for(int j:G[i]){
if(color[i]==1)
T[i].push_back(j);
else
T[j].push_back(i);
}
}
for(int i=1;i<=n;i++){
if(color[i]==1){
idx++;
if(hungary(match,i,-1,-1))
ans++;
}
}
for(int i=1;i<=n;i++){
if(color[i]==2){
memset(match2,0,sizeof match2);
int nowans=0;
for(int j=1;j<=n;j++){
if(color[j]==1){
idx++;
if(hungary(match2,j,match[i],i))
nowans++;
}
}
if(nowans<ans)
Ans.push_back({min(match[i],i),max(match[i],i)});
}
}
sort(Ans.begin(),Ans.end());
cout<<Ans.size()<<'\n';
for(auto i:Ans)
cout<<i.first<<' '<<i.second<<'\n';
return 0;
}
总结：
-
寻找一个网络中两两之间有关系的一群东西，考虑最大团。
-
最大团问题分析补图。
-
做题从概念出发。
P2423
根据朋友圈的定义我们容易发现这是一个最大团问题，但是哪来的二分图？？？
进行一个条件的解读：
-
A 国：对于两个友善值为 \(a,b\) 的 A 国人，\((a\mathbin{\mathrm{xor}} b) \bmod 2=1\) 这个条件意味着若它们是朋友，则 \(a,b\) 奇偶性不同。
-
B 国：反之。第二个条件无需解读，直接判即可。
那么 B 国的补图就是 \(a,b\) 奇偶性不同的连边，我们把奇数点看作左部点，偶数点看作右部点，二分图出来了。
显然不考虑 A 国的时候，本题答案即为 \(B\) 国的最大团。
但是 A 国加进来怎么办？这启发我们去挖掘性质。
因为 A 国是奇偶不同连边，根据抽屉原理，A 国一定不能加进来超过 \(2\) 人，因为到了第 \(3\) 个人就一定会与前两个人中的某一个不连边，形成不了最大团。
那么我们暴力地去枚举 A 国加哪些人（如果加两个人，则他们俩必须是朋友），然后将他们所连接的 B 国人求一次最大团即可。
但是有一种方法是不行的，就是把 B 国的人全放进来求一遍最大团，然后再选 A 国人加入。一方面我们无法知道最大团的方案，也就无法验证其正确性；另一方面，将 B 国人全求一遍最大团不一定最优，我们完全可以少选几个然后多加几个 A 国人进来。
同样，将 A 国人加入和 B 国人一起求最大团更是不行的，因为我们无法保证 A 国人加进来以后还是二分图。
为什么我要讲以上两种错误方法呢，还不是因为老师的误导（光速逃）。
综上，本题是巨大困难图论题，并且结合了数学知识，考察了我们解读条件、挖掘性质的能力，还要求我们具有转换角度的思想（因为正常人都会往错误方法一想），确实是一道极好的题目。
标签：Living,cur,int,国人,mm,补图,91,Dream,最大 From： https://www.cnblogs.com/XOF-0-0/p/18675255