davidwang's Blog

首先这样一道题我这样的蒟蒻肯定是不会的了

只有卢爷很快就能秒掉这种题目拉

下面是我们的对话：

 “卢爷，4160怎么做？”

“4160,什么题阿？”于是打开bzoj开始翻"哦，这道题阿，我也不会做"

"那您是怎么A掉的？" "就是随便猜了个性质，就是求出独立集覆盖就可以了"

“为什么？” “你感受以下就是可以的”

于是我感受了一下

然后就没了

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <deque>
#include <iostream>
using namespace std;
#define LL long long
#define X first
#define Y second
template<typename T>
inline T sqr(const T &x){ return x*x; }
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 15;
int a[N][N];
int list[200];
int f[1<<N],ok[1<<N];
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	int m=read(),n=0;
	char s1[3],s2[3];
	memset(list,-1,sizeof(list));
	for (int i=1;i<=m;i++){
		scanf("%s%s",s1,s2);
		if (list[s1[0]]==-1) list[s1[0]]=n++;
		if (list[s2[0]]==-1) list[s2[0]]=n++;
		int x=list[s1[0]],y=list[s2[0]];
		a[x][y]=a[y][x]=1;
	}
	for (int s=1;s<(1<<n);s++){
		ok[s]=1;
		for (int j=0;j<n;j++)
			if (s>>j&1)
				for (int k=0;k<n;k++)
					if (s>>k&1)
						if (a[j][k] || a[k][j])
							ok[s]=0;	
	}
	for (int s=1;s<(1<<n);s++){
		f[s]=100000;
		if (ok[s]){
			f[s]=1; continue;
		}
		for (int s0=(s-1)&s;s0;s0=(s0-1)&s){
			if (ok[s0] && f[s^s0]<f[s]) f[s]=f[s^s0]+1;
		}
	}
	printf("%d\n",f[(1<<n)-1]-2);
	return 0; 
}