【Gym - 101915D】Largest Group(二分图最大团,状压dp)
題干:
大黑山上有小小民和小小濤兩種物種,山東人小李想要研究這兩種物種的關(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 2Sample 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)題。
- 上一篇: 【蓝桥官网试题 - 算法提高】chang
- 下一篇: 现在有数字人民币了吗?数字人民币跟比特币