題干：

大黑山上有小小民和小小濤兩種物種，山東人小李想要研究這兩種物種的關(guān)系

奇怪的是大黑山上有相同數(shù)量的小小民和小小濤。小李數(shù)了數(shù)一共有 P 個(gè)，小李分別給P個(gè)小小民和小小濤編號(hào) 1 - P 號(hào)，已知每對(duì)小小民之間都是好朋友，每對(duì)小小濤之間也都是好朋友，但是 i 號(hào)小小民和 j 號(hào)小小濤不一定是好朋友

山東人小李想要知道在這個(gè)物種間最大的友好群體的物種數(shù)量(在這個(gè)群體中任意兩個(gè)生物都是好朋友)，你能幫小李解決這個(gè)難題嘛？

Input

第一行一個(gè)整數(shù)T，代表測(cè)試數(shù)據(jù)數(shù)量

每個(gè)測(cè)試數(shù)據(jù)第一行有兩個(gè)整數(shù) P N ,大黑山上小小民或者小小濤的數(shù)量 P ，和他們之間有 N 個(gè)關(guān)系 ( 1<= P <=20 ),( 0<= N <= P^2 )

接下來(lái) N 行每行兩個(gè)整數(shù) mi ti 表示 mi 編號(hào)的小小民和 ti 編號(hào)的小小濤是好朋友

Output

對(duì)于每個(gè)測(cè)試數(shù)據(jù)，輸出一個(gè)整數(shù)表示最大的友好群體中生物的數(shù)量

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

解題報(bào)告：

? ?直接跑補(bǔ)圖最大獨(dú)立集就行了=二分圖中頂點(diǎn)數(shù)-最小點(diǎn)覆蓋。

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竟然能過(guò)）

狀壓dp，復(fù)雜度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;//記錄當(dāng)前男生情況下可以獲得的所有女生 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 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【Gym - 101915D】Largest Group（二分图最大团，状压dp）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。