2018 Multi-University Training Contest 3 C Dynamic Graph Matching(hdu 6321)(状压dp)
程序员文章站
2022-06-09 18:58:12
...
题目链接:hdu 6321 Problem C. Dynamic Graph Matching
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
题意:
思路:状压dp呢是不会的,看呢也是看不太懂的,看懂了以后也是不一定会做的,但是题解呢还是要写一下的,写不出呢就只能把题解截个图凑合过这样子,希望有朝一日我能学会
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define mod (1e9+7)
using namespace std;
typedef long long ll;
int dp[30004][2000];//dp[i][j]:i这个操作后,j这个点集合已经匹配的方案数
int cntone[2000];//1的个数
int main(){
int t;
scanf("%d",&t);
for(int i=1;i<=1050;i++){
cntone[i]=cntone[i>>1]+(i&1);
}
while(t--){
int n,m;
scanf("%d%d",&n,&m);
memset(dp,0,sizeof(dp));
for(int i=0;i<(1<<n);i++){
dp[0][i]=1;
}
for(int i=1;i<=m;i++){
char s[10];
int u,v;
scanf("%s%d%d",s,&u,&v);
u--;v--;
int uv=(1<<u)|(1<<v);//uv表示含有点u和v的集合
for(int j=(1<<n)-1;j>=0;j--){
if((j&uv)!=uv)continue;//j集合不包含uv
for(int k=1;k<=cntone[j];k++){
if(s[0]=='+'){
dp[k][j]+=dp[k-1][j^uv];
}
else{
dp[k][j]-=(dp[k-1][j^uv]-mod);
}
if(dp[k][j]>=mod)dp[k][j]-=mod;
}
}
for(int j=1;j<=n/2;j++){
if(j==n/2)printf("%d\n",dp[j][(1<<n)-1]);
else printf("%d ",dp[j][(1<<n)-1]);
}
}
}
return 0;
}