[Codeforces1105E][一般图最大匹配]E. Helping Hiasat

垃圾比赛，毁我青春
居然有人在网络赛出NPC问题。。真是烦

首先， 别管什么这题每次加入的是一个团
如果题目里面按

1
2 …
2 …
1

的形式加进来，那么就是一条一条边了。。
那么说白了就是给你m个点，n条边（可能大量重边） 的图找最大独立集
首先独立集往往转化为补图的最大团来做

相信大家都知道这个东西是NPC问题
那么就直接开始爆搜。。
如果考场上不会怎么办？上网找题解啊，这么经典的问题，找到好的剪枝就能AC
然而我一开始抄了一个还没过去23333

inline void dfs(int x,int cnt)
{
    if(x>tot)	{
    ans=cnt;return;}bool tf=1;for(int i=1;i<x;++i){
    if(in[i]&&!f[i][x]){
    tf=0;break;}}if(tf){
    in[x]=1;dfs(x+1,cnt+1);in[x]=0;}if(cnt+tot-x>ans) dfs(x+1,cnt);
}

这里只用到了最优性剪枝，也就是如果这个点后面所有点都选上也没有答案大，那么就不用继续了
然而出题人并没有这么简单。。他可不想让你随便搜搜就过了
于是找到了另外一种爆搜
就是从按编号从大往小搜，那么我们可以记录一个$cn{t}_i$表示$i$这个后缀的最大独立集是多少
那么我们就可以把上一个的最优性剪枝优化为，如果选了后面的最大独立集都不够大，那么就可以退出了，也就是把上面的全部选上更细化了
没错，就是魔改的。。

bool dfs(int x, int now)
{for (int I = x + 1; I <= m; I++){if (cnt[I] + now <= ans) return 0;if (f[x][I]){bool tf = 0;for (int j = 0; j < now; j++)if (!f[I][sta[j]]){tf = 1;break;}if (!tf){sta[now] = I;if (dfs(I, now + 1)) return 1;}}}if (now > ans){ans = now;return 1;}return 0;
}

然后就可以通过本题了。。
复杂度的话不太清楚，反正40跑得过就是了。。
当然，也有知道复杂度的做法，就是折半状压DP
$f_i$表示前$\frac{m}{2}$个点，某个点集的最大独立集
$g_j$表示后$\frac{m}{2}$个点，某个点集的最大独立集
每一次，我们暴力枚举$i$，然后找到一个最大的$j$，使得$i,j$之间没有边，那么就更新答案$ans=max(ans,f_i+g_j)$即可
那么复杂度就是$O(2^{m/2}?m)$了。。
也可以通过本题
这个方法没打。。自己写写吧。。应该也不难

然后就没什么了
为什么要出爆搜题啊。。
感觉就是因为出题人想不到什么题可以出了就出了一个爆搜题