http://acm.hdu.edu.cn/showproblem.php?pid=6321
Problem Description In the mathematical discipline of graph theory, a matching in a graph is a set of edges without common vertices. You are given an undirected graph with n vertices, labeled by 1,2,…,n. Initially the graph has no edges. There are 2 kinds of operations : +u v, add an edge (u,v) into the graph, multiple edges between same pair of vertices are allowed. -u v, remove an edge (u,v), it is guaranteed that there are at least one such edge in the graph. Your task is to compute the number of matchings with exactly k edges after each operation for k=1,2,3,…,n2. Note that multiple edges between same pair of vertices are considered different.
题意：n（<=10）个点，m（3万）次修改，每次增或删一条边，并询问当前恰好k条边（k<=n/2）的匹配数。 思路：状压，设 f ( s ) ： 覆 盖 点 为 s 的 匹 配 数 f(s)：覆盖点为s的匹配数 f(s)：覆盖点为s的匹配数，在之前图的基础上，考虑加一条边的影响，那么就考虑使用这条边连两点u，v，然后加上剩余的连法，即 f [ s ] + = f [ s f[s]+=f[s f[s]+=f[s x o r ( 1 < < u ) x o r ( 1 < < v ) ] xor(1<<u) xor (1<<v)] xor(1<<u)xor(1<<v)]，减边也是一样的道理。 注意从后往前更新，滚动数组。 复杂度 O ( T ∗ m ∗ 2 n ) O(T*m*2^n) O(T∗m∗2n)
#include<bits/stdc++.h> using namespace std; #define mod 1000000007 int T,n,m; int f[1<<10],cnt[1<<10],ans[6]; void init() { for(int s=0;s<(1<<10);s++) { int i=s,c=0; while(i) { if(i&1)c++; i>>=1; } cnt[s]=c; } } int main() { ///freopen("input.in","r",stdin); cin>>T; init(); while(T--) { cin>>n>>m; memset(f,0,sizeof(f)); f[0]=1; while(m--) { char op[5]; int u,v; cin>>op>>u>>v; u--;v--; for(int s=(1<<n)-1;s>=0;s--)if((s&(1<<u))&&(s&(1<<v))) { if(op[0]=='+')f[s]=(f[s]+f[s^(1<<u)^(1<<v)])%mod; else f[s]=(f[s]-f[s^(1<<u)^(1<<v)]+mod)%mod; } memset(ans,0,sizeof(ans)); for(int s=1;s<(1<<n);s++)ans[cnt[s]/2]+=f[s],ans[cnt[s]/2]%=mod; printf("%d",ans[1]); for(int i=2;i<=n/2;i++)printf(" %d",ans[i]); putchar('\n'); } } return 0; }