HDU1530 Maximum Clique dp
正解:dp
解题报告:
这儿是传送门
又是个神仙题趴QAQ
这题就直接说解法辣?主要是思想比较难,真要说有什么不懂的知识点嘛也没有,所以也就没什么好另外先提一下的知识点QAQ
首先取反,就变成了求最大独立集,就方便求一些,这是第一个小技巧(记得总结下QAQ!哪天我要写个图论技巧总结QAQ
然后把所有点平均分成两份,A和B
对A预处理出它的所有子集的最大独立集,记录下来
这里可以用dp做一下,对子集T中的任意一点v,不选就是从dp[T-v]转移来,选就是从dp[T-v-u]转移来(u是所有和v有连边的点
然后可以顺便记个方案数
然后对于B我们枚举独立集,把A中和独立集有边相连的点都删了,答案就是dp[剩余的点]
(顺便补个细节
把边状压起来
这样查询什么的时候就可以O(1)地处理掉
下面的代码是还未完成版只是mk下而已QAQ
over
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rp(i,x,y) for(register ll i=x;i<=y;++i)
#define lowbit(x) x&(-x)
ll n,m,zt[60],dp[68000000],sz[68000000];
inline ll read()
{
register char ch=getchar();register ll x=0;register bool y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=getchar();
if(ch=='-')ch=getchar(),y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
return y?x:-x;
}
int main()
{
n=read();m=read();rp(i,1,n)zt[i]=(1<<n)-1;rp(i,1,m){ll t1=read(),t2=read();zt[t1]^=(1<<t2);zt[t2]^=(1<<t1);}
rp(i,1,25)dp[1<<i]=1,sz[1<<i]=1;
rp(i,2,(1<<26)-1)
{
ll tmp=i;
while(tmp)
{
ll v=lowbit(tmp);tmp-=v;
ll sz1=sz[i^v]+1,nm1=dp[i^v];if(sz1>sz[i])sz[i]=sz1;if(sz1==sz[i])dp[i]+=nm1;
ll sz2=sz[(i^v)&zt[v]],nm2=dp[(i^v)&zt[v]];if(sz2>sz[i])sz[i]=sz2;if(sz2==sz[i])dp[i]+=nm2;
}
}
/*其实我现在要做应该还是做得出来的了,,,就是在右边枚举独立集然后删了所有有连边的点然后查看sz就好了,,,但是我实在不想打了,,,明天打趴QAQ*/
return 0;
}