AtCoder Beginner Contest 187 F - Close Group(状态压缩动态规划)

差亿点AK，只怪没学过状态压缩动态规划，呀嘞呀嘞dazei
枚举一个图的子图：

for(int i=n;i;i=(i-1)&n)
{
      //i就是n的子图
}

AtCoder Beginner Contest 187 F - Close Group

题意：给一个n(n<=18)节点m条边的图，删除几个边后，使它变成几个连通子图，求最少能够变成几个子图，并且全是完全图
题解：首先枚举所有子图，如果是完全图，标记dp[i]=1，然后从小到大枚举，对一个非完全子图，再枚举其子图更新答案，由于是从小到大枚举，因此当前子图的子图肯定已经更新完了，所以可放心dp

#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ll long long
#define pb push_back
inline int read(){int x;scanf("%d",&x);return x;}
int eg[20][20],dp[1<<N];
void solve()
{
	int n=read(),m=read();
	f(i,1,m){
		int x=read(),y=read();
		eg[x][y]=eg[y][x]=1;
	}
	int sum=(1<<n)-1;
	dp[0]=999999;
	for(int i=1;i<=sum;++i)
	{
		vector<int>edge;
		for(int j=0;j<n;j++) if(i&(1<<j)) edge.pb(j+1);
		int flag=1;
		for(int j=0;flag&&j<edge.size();++j)
			for(int k=j+1;flag&&k<edge.size();++k)
				if(!eg[edge[j]][edge[k]]) flag=0;
		if(flag) dp[i]=1;
		else dp[i]=999999; 
	}
	for(int i=1;i<=sum;++i)
	{
		if(dp[i]==1) continue;
		for(int j=i;j;j=(j-1)&i)
		{
			dp[i]=min(dp[i],dp[j]+dp[j^i]);
		}
	}
	cout<<dp[sum]<<endl;
}
int main()
{
	int T=1;
	while(T--) solve();
	return 0;
} 

AtCoder Beginner Contest 187 F - Close Group(状态压缩动态规划)

原文：https://www.cnblogs.com/Tiork/p/14224998.html