题干：

大黑山上有小小民和小小涛两种物种，山东人小李想要研究这两种物种的关系

奇怪的是大黑山上有相同数量的小小民和小小涛。小李数了数一共有 P 个，小李分别给P个小小民和小小涛编号 1 - P 号，已知每对小小民之间都是好朋友，每对小小涛之间也都是好朋友，但是 i 号小小民和 j 号小小涛不一定是好朋友

山东人小李想要知道在这个物种间最大的友好群体的物种数量(在这个群体中任意两个生物都是好朋友)，你能帮小李解决这个难题嘛？

Input

第一行一个整数T，代表测试数据数量

每个测试数据第一行有两个整数 P N ,大黑山上小小民或者小小涛的数量 P ，和他们之间有 N 个关系 ( 1<= P <=20 ),( 0<= N <= P^2 )

接下来 N 行每行两个整数 mi ti 表示 mi 编号的小小民和 ti 编号的小小涛是好朋友

Output

对于每个测试数据，输出一个整数表示最大的友好群体中生物的数量

Sample Input

2
4 5
1 2
2 2
3 2
4 2
1 4
3 4
1 2
2 1
1 1
2 2

Sample Output

5
4

解题报告：

   直接跑补图最大独立集就行了=二分图中顶点数-最小点覆盖。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
int p,n;
bool line[22][22];
int nxt[22];
int use[22];
bool find(int x) {
	for(int i = 1; i<=p; i++) {
		if(line[x][i] && use[i] == 0) {
			use[i] = 1;
			if(nxt[i] == 0 || find(nxt[i])) {
				nxt[i] = x;
				return 1;
			}
		} 
	}
	return 0 ;
}
int match() {
	int res = 0;
	for(int i = 1; i<=p; i++) {
		memset(use,0,sizeof use);
		if(find(i)) res++;
	}
	return res;
}
int main()
{
	int t;
	cin>>t;
	while(t--) {
		memset(line,1,sizeof line);
		memset(nxt,0,sizeof nxt);
		scanf("%d%d",&p,&n);
		for(int a,b,i = 1; i<=n; i++) {
			scanf("%d%d",&a,&b);
			line[a][b]=0;
		}
		printf("%d\n",2*p-match());
	} 
	return 0 ;
}

法二：（1400ms竟然能过）

状压dp，复杂度O(n*2^n)枚举

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
int bit[22];
int lowbit(int x) {return x&-x;}
int main()
{
	int t,p,n;
	cin>>t;
	while(t--) {
		scanf("%d%d",&p,&n);
		memset(bit,0,sizeof bit);
		for(int a,b,i = 1; i<=n; i++) {
			scanf("%d%d",&a,&b);
			a--;b--;
			bit[a] |= 1<<b;
		}
		int up = 1<<p,ans = 0;
		for(int sta = 0; sta<up; sta++) {//枚举选择了哪些男生 
			int tmp = up-1;//记录当前男生情况下可以获得的所有女生 
			for(int i = 0; i<p; i++) {
				if(sta&(1<<i)) tmp &= bit[i];
			}
			int sum = 0;
			for(int i = tmp; i!=0; i-=lowbit(i)) {
				sum++;
			}
			for(int i = sta; i!=0; i-=lowbit(i)) sum++;			
			ans = max(ans,sum);
		}
		printf("%d\n",ans);
	}
	return 0 ;
}