HDU 6321 Dynamic Graph Matching

题目解析

题意：给一个图有N个点和若干个询问，每个询问增或者删一条边，每个询问输出选择1~N/2条不相交的边的方案数。

题解：状压DP

代码

#include<bits/stdc++.h>

#define CLR(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;

ll dp[1<<10];

ll ans[6];

int main()

{

//    freopen("c.in","r",stdin);

//    freopen("ans.txt","w",stdout);

    int t,n,m,x,y,cnt;

    ll tmp;

    char s[2];

    scanf("%d",&t);

    while(t--){

        scanf("%d%d",&n,&m);

        CLR(ans,0);

        CLR(dp,0);

        dp[0] = 1;

        for(int i = 1; i <= m; i++){

            scanf("%s %d %d",s,&x,&y);

            if( s[0] == '+'){

                for(int i = 0;i < (1<<n); i++){

                    if((i&(1<<(x-1))) && (i&(1<<(y-1)))){

                        tmp = dp[i];

                        dp[i] = (dp[i] + dp[(i^(1<<(x-1))^(1<<(y-1)))])%mod;

                        cnt = 0;

                        for(int j = 0; j < n; j++){

                            if(i&(1<<j)) cnt++;

                        }

                        ans[cnt/2] = (ans[cnt/2] + (dp[i]-tmp)%mod + mod )%mod;

                    }

                }

            }

            if( s[0] == '-'){

                for(int i = 0;i < (1<<n); i++){

                    if((i&(1<<(x-1))) && (i&(1<<(y-1)))){

                        tmp = dp[i];

                        dp[i] = (dp[i]-dp[(i^(1<<(x-1))^(1<<(y-1)))] + mod)%mod;

                        cnt = 0;

                        for(int j = 0; j < n; j++){

                            if(i&(1<<j)) cnt++;

                        }

                        ans[cnt/2] = (ans[cnt/2]+(dp[i]-tmp)%mod + mod)%mod;

                    }

                }

            }

            printf("%d",ans[1]%mod);

            for(int i = 2; i <= n/2; i++){

                printf(" %d",ans[i]%mod);

            }

            printf("\n");

        }

    }

    return 0;

}

/*

1

4 8

+ 1 2

+ 3 4

+ 1 3

+ 2 4

- 1 2

- 3 4

+ 1 2

+ 3 4

*/