HDU 6321 Dynamic Graph Matching (状压DP)
Problem C. Dynamic Graph Matching
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1796 Accepted Submission(s): 731Problem 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个点和若干个询问，每个询问增或者删一条边，每个询问输出选择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
*/