HDU6321 Problem C. Dynamic Graph Matching

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.

 

 

Input

The first line of the input contains an integer T(1≤T≤10) , denoting the number of test cases.
In each test case, there are 2 integers n,m(2≤n≤10,nmod2=0,1≤m≤30000) , denoting the number of vertices and operations.
For the next m lines, each line describes an operation, and it is guaranteed that 1≤u<v≤n .

 

 

Output

For each operation, print a single line containing n2 integers, denoting the answer for k=1,2,3,...,n2 . Since the answer may be very large, please print the answer modulo 109+7 .

 

 

Sample Input

1 4 8 + 1 2 + 3 4 + 1 3 + 2 4 - 1 2 - 3 4 + 1 2 + 3 4

 

 

Sample Output

1 0 2 1 3 1 4 2 3 1 2 1 3 1 4 2

题意：给定n个点的无向图，m次加边或者删边操作。

      每次操作后统计包含1，2，3 ... n/2条边的匹配。

 

思路分析：

         考虑所有只有一条边的匹配。那么这种匹配肯定只涉及2个顶点。考虑二进制压缩。

那么对于最多10个点的情况。取10位二进制表示10个顶点，那么所有只有一条边的匹配就可以表示为1100000000，   0101000000 等形式，而且不会遗漏。同样道理对于2条边的情况，就可以用只有四个1的10位二进制数表示了。因此，考虑dp[1025]表示各种情况下的匹配数。初始dp[0] = 1; 因为每次只加一条边。 那么每加一条边，我们就得更新各种情况下的匹配数目了。具体操作就是这样的： 每次加边涉及两个点，不妨设二进制下表示为s= 1100000000，那么他能更新那些匹配？考虑每种情况i 若 s&i == 0 说   明他们没共工顶点吧。那么s|i的状态就能被更新了。因为在s|i中多出了选择新加边再选择i状态下所有匹配的方案数。

      因此，dp[s|i] += dp[i];

      同样道理，再删除边的时候，只要做相应的撤销就好了。

最后每次询问只要加和对应的所有情况就好了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 1025;
ll dp[maxn];
int bin[maxn];
char s[25];
ll ans[50];
int main()
{
    for(int i = 0; i < 1024; i++)
    {
        bin[i] = __builtin_popcount(i);
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        memset(dp,0,sizeof(dp));
        dp[0] = 1;
        int up = (1<<n)-1;
        while(m--)
        {
            int x,y;
            scanf("%s%d%d",s,&x,&y);
            int tmp = (1<<(x-1))|(1<<(y-1));
            if(s[0] == '+')
            {
                for(int i = up; i >= 0; i--) 
                {
                    if((i&tmp) == 0) dp[i|tmp] = (dp[i|tmp]+dp[i])%mod;
                }
            }
            else 
            {
                for(int i = 0; i <= up; i++)
                {
                    if((i&tmp) == 0) dp[i|tmp] =(dp[i|tmp]-dp[i]+mod)%mod;;
                }
            }
            memset(ans,0,sizeof(ans));
            for(int i = 0; i <= up; i++)
            {
                ans[bin[i]] += dp[i];
                ans[bin[i]] %= mod;
            }
            for(int i = 2; i <= n; i+=2)
            {
                printf(i == n ? "%lld\n" : "%lld ",ans[i]);
            }
        } 
    }
    return 0;
}