欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

2018 Multi-University Training Contest 3 C Dynamic Graph Matching(hdu 6321)(状压dp)

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

 

题意:

2018 Multi-University Training Contest 3 C Dynamic Graph Matching(hdu 6321)(状压dp)

思路:状压dp呢是不会的,看呢也是看不太懂的,看懂了以后也是不一定会做的,但是题解呢还是要写一下的,写不出呢就只能把题解截个图凑合过这样子,希望有朝一日我能学会

2018 Multi-University Training Contest 3 C Dynamic Graph Matching(hdu 6321)(状压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;
}