• C. Dynamic Graph Matching

C. Dynamic Graph Matching

题意

给定一个 n 个点的无向图，m 次加边或者删边操作。
在每次操作后统计有多少个匹配包含 k = 1, 2, …,n/2 条边。
匹配的定义： 边的集合，没有共同的顶点

分析

先把匹配的概念转换，n个边的匹配，就是n条边没有共同的顶点，那就是2*n个点，没有共同的边
那么问题就转化成点,1,2,3....n/2$1,2,\mathrm{3....}n/2$ 条边，其实就是2,4,6,8,..n$2,4,6,8,..n$ 个点的集合，集合中的点没有共同的边

首先这是一个dp问题
阶段： 每一个加边或者减边的操作
状态： S 集合 (S 集合包含哪些点）
状态转移方程

F[0]=1$$F[0]=1$$

F[S]=（u，v属于S）{F[S]+F[S−u−v]F[S]−F[S−u−v]加边减边$$F[S]=（u，v属于S）\{\begin{array}{ll}F[S]+F[S-u-v]& 加边\\ F[S]-F[S-u-v]& 减边\end{array}$$

加边比较好理解就是加F[S]$F[S]$ 由两部分组成，一部分是之前S集合匹配的个数F[S],一部分是之前不含有(u,v) 顶点，现在加入(u,v) 顶点形成S集合 F[S-u-v]
减边的时候可以这样理解，假设上一次刚好加的就是这条边，那么使用的是+操作，这回把上一次加上的减去这样理解

参考代码

附上和标程几乎一模一样的代码

const int N = (1<<10);
int T,n,m,u,v,S;
int cnt[N];
int F[N];
int ans[15];
// 状态转移方程
// 加边的时候                     F[S]  = F[S]+F[S-u-v]
// 减去这条边的时候把原来加的减去 F[S]  = F[S]-F[S-v-v]
int main(void)
{
   for(int i = 0;i < N; ++i) cnt[i] = __builtin_popcount(i);
   scanf("%d",&T);
   while(T--){
    scanf("%d %d",&n,&m);
    int all = 1<<n;
    for(int i = 0;i < all; ++i) F[i] = 0;
    F[0] = 1;
    while(m--){
        char c[10];
        scanf("%s %d%d",c,&u,&v);
    //  cout<<c<<u<<v;
        u--,v--;
        S = (1<<u)|(1<<v);
        if(c[0] == '+'){
                for(int i = 0;i < all; ++i){
                    if(!(S&i)) F[i^S] =( F[i^S] + F[i])%mod;
                  }
           }
        else {
               for(int i = 0;i < all; ++i){
                   if(!(S&i)) F[i^S] = (F[i^S] - F[i])%mod;
               }
        }
        for(int i = 0;i <= n; ++i)
           ans[i] = 0;
        for(int i = 0;i < all; ++i)
           ans[cnt[i]] = (ans[cnt[i]]+F[i])%mod;
        for(int i = 2;i <= n; i += 2){
           printf("%d%c",(ans[i]%mod+mod)%mod," \n"[i==n]);
          }
       }

   }

   return 0;
}