hdu 6321-Dynamic Graph Matching

6321-Dynamic Graph Matching

题意：给定一个n 个点的无向图，m 次加边或者删边操作。在每次操作后统计有多少个匹配包含k = 1, 2, ..., n/2 条边。

题解：状压DP。先放官方题解，我觉得讲的蛮清楚的。

我再说一下我的理解，首先S表示的是一个集合，里面表示的是哪个点被选了哪个点没有，因为n最多10，所以我们可以用二进制来表示一个集合里面的情况，第i位为0表示第i个数没有选进集合，为1表示在集合中。这样我们开的 dp数组（就是上面的f，我习惯用dp），只用开到1<<10就好了，对于加边x,y操作，有这两条边的一定是S的第(1<<x)和(1<<y)位置上为1，令s=(1<<x)|(1<<y)；从大到小遍历每一个S，如果(s&S)==0，那就说明s上为1的位置S为0，S是不是就是上面表达式中的（S − u − v）//不要混乱，两个大S不一样。所以对于每个S，如果满足(s&S)==0，我们就可以进行状态转移：dp[s^S]=dp[s^S]+dp[S], 这里的s^S表示的是在S集合中加上x,y两个点。对于删边操作，和加边一样，知道了怎么表示（S − u − v），我们就可以按照状态转移方程进行转移了，但是注意删边是从小到大遍历S。这里还有个需要注意的点是：因为最后的答案是以点来分类的，我们需要统计每个S中的点的个数这样才知道什么时候该输出哪些答案，所以我们要提前预处理一下，开一个cnt [i] 数组来表示i集合中有几个点，也就是数字 i 的二进制中有几个1，左后合并计数的时候就可以直接合并了。看了代码一起理解会更好

附上代码：

#include<cstdio>
const int maxn=1<<10,P=1000000007;
int T,n,m,all,i,x,y,S,dp[maxn],cnt[maxn],ans[maxn];
char c[9];
inline void add(int&a,int b)
{
    a=a+b<P?a+b:a+b-P;//取模
}
inline void del(int&a,int b)
{
    a=a-b>=0?a-b:a-b+P;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        all=1<<n;//最多有多少位数
        for(i=0; i<all; i++)
            dp[i]=0,cnt[i]=__builtin_popcount(i);//计算一个32位无符号整数有多少个位为1
        dp[0]=1;
        while(m--)//m次操作
        {
            scanf("%s%d%d",c,&x,&y);
            x--,y--;
            S=(1<<x)|(1<<y);//如果是不同的两个点异或起来为1 的位置始终为1
            if(c[0]=='+')
            {
                for(i=all-1; ~i; i--)//加边要从大到小遍历
                    if(!(i&S))//与起来等于0相当于s上不为0的两个位置i上为0.
                        add(dp[i^S],dp[i]);//i异或上s表示i加上s中的两个点
                    //dp[s]=dp[s]+dp[s-u-v];
            }
            else
            {
                for(i=0; i<all; i++)//删边从小到大遍历
                    if(!(i&S))
                       del(dp[i^S],dp[i]);
            }
            for(i=1; i<=n; i++)
                ans[i]=0;//
            for(i=1; i<all; i++)
                add(ans[cnt[i]],dp[i]);//合并计数
            for(i=2; i<=n; i+=2)
                printf("%d%c",ans[i],i<n?' ':'\n');
        }
    }
}