13

AtCoder Beginner Contest 187 F - Close Group

 3 years ago
source link: http://www.cnblogs.com/StarRoadTang/p/14224930.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

题目链接

点我跳转

题目大意

给你一张完全图，你可以删除任意数量的边

要求删除完后剩余的所有子图必须是完全图

问完全子图数量最少是多少

解题思路

定义 \(ok[i]\) 表示状态为 \(i\) 时所对应的点构成的图是否为完全图 ( \(1\) 为是 , \(0\) 为否)

判断完全图可直接暴力枚举任意两点检查是否有边

定义 \(dp[i]\) 表示状态为 \(i\) 时所对应的点构成的所有子图都为完全图，且子图数最小

其中 \(dp[0] = 0\)

那么不难得到当 \(ok[j] = 1\) 时

\(dp[i] = min(dp[i] , dp[i\) ^ \(j] + 1)\) , （ \(j\) 为 \(i\) 的子集 ）

答案为 \(dp[1 << n - 1]\)

AC_Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1LL << 19 , M = 20;
int n , m , dp[N] , ok[N] , g[M][M];
signed main()
{
	cin >> n >> m;
	for(int i = 1 ; i <= m ; i ++)
	{
		int x , y;
		cin >> x >> y;
		g[x][y] = g[y][x] = 1;
 	}
 	int sum = 1 << n;
	for(int i = 0 ; i < sum ; i ++)
	{
		ok[i] = 1;
		for(int j = 1 ; j <= n ; j ++) if(i >> (j - 1) & 1) 
		{
			for(int k = j + 1 ; k <= n ; k ++) if(i >> (k - 1) & 1)		
			{
				if(!g[j][k]) { ok[i] = 0 ; break ; }		
			}
			if(!ok[i]) break ;
		} 
		dp[i] = 1e9; 
	}
	dp[0] = 0;
	for(int i = 0 ; i < sum ; i ++)
	{
		for(int j = i ; j ; j = (j - 1) & i) if(ok[j]) 
		{
			dp[i] = min(dp[i] , dp[i ^ j] + 1);
		}
	}
	cout << dp[sum - 1] << '\n';
	return 0;
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK