題意：給定一個N個點的零圖，M次操作，添加或刪除一條邊，每一次操作以后，打印用1,2,…N/2條邊構成的匹配數。
分析：因為N的范圍很小，所以可以把點的枚舉狀態用二進制表示集合。用一維數組dp[S]表示二進制集合為S的點集的匹配數。
每次加邊操作，從大到小遍歷集合，dp[S]+=dp[S-u-v]；刪邊操作，從小到大遍歷集合，dp[S]-=dp[S-u-v]。
預處理出每個1024之內每個數對應二進制含有1的個數，每次記錄答案就將每個dp[S]加到ans[S]對應的二進制個數]中。

#include<bits/stdc++.h> using namespace std; const int maxn =1030; const int mod = 1e9+7; typedef long long LL; void add(int &a,int b){a=a+b<mod?a+b:a+b-mod;} void del(int &a,int b){a=a-b<0?a-b+mod:a-b;} int dp[maxn],ans[15],cnt[maxn];int main() {int T,N,M,u,v;char op[5];scanf("%d",&T);while(T--){scanf("%d%d",&N,&M);int tot=1<<N;for(int i=0;i<tot;++i){dp[i]=0;cnt[i] = __builtin_popcount(i);//統計二進制中1的個數}dp[0]=1;while(M--){scanf("%s%d%d",op,&u,&v);memset(ans,0,sizeof(ans));u--,v--;int S = (1<<u)|(1<<v); //取只包含u,v的集合if(op[0]=='+'){for(int t=tot-1;~t;--t)if(!(t&S)) add(dp[t^S],dp[t]); //加上原來不包含的u,v的集合的匹配數}else{for(int t=0;t<tot;++t)if(!(t&S)) del(dp[t^S],dp[t]); //減去原來不包含u,v的集合的匹配數}for(int i=1;i<tot;++i) add(ans[cnt[i]],dp[i]);for(int i=2;i<=N;i+=2) printf("%d%c",ans[i],i<N?' ':'\n');}}return 0; }

轉載于:https://www.cnblogs.com/ffgcc/p/10546347.html

總結

以上是生活随笔為你收集整理的HDU 6321 Problem C. Dynamic Graph Matching (状压dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。