hdu 5713(状态压缩DP)

要进行两次dp，

第一个，dp[i],1<=i<=(1<<n)

其中用i的二进制形式表示已选择的点。

dp[i] 用来保存i中的点构成一个连通块，边集多少种可能。

转移方程：

        save[0] = 1;//这里用save[i]表示dp[i]for(int i=1;i<(1<<n);i++){int ti = i-lowbit(i); //一定选择最后一个点，使之有序int j = ti;long long tmp=0;//问题转化为对立问题，记录有多少不连通边集的情况，all[i]表示i中的点，边集的所有可能情况。for(;j>0;j=(j-1)&ti){tmp += save[i-j]*all[j];tmp %= MOD;}save[i] = (all[i]-tmp+MOD)%MOD;}    

第二次dp，套路基本相同。

dp[i][j] 表示恰有（i+1）个连通块，且含j中的点的所有可能。

转移方程：

　　　　　for(int i=1;i<kk;i++){for(int j=1;j<(1<<n);j++){int tj= j-lowbit(j);for(int k=tj; k>0;k = (k-1)&tj ){dp[i][j] += dp[i-1][k]*save[j-k];dp[i][j] %= MOD;}}}

//
//  main.cpp
//  Astar160529
//
//  Created by 陈加寿 on 16/5/29.
//  Copyright © 2016年 chenhuan001. All rights reserved.
//

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;#define MOD 1000000009long long dp[15][1<<14];
int mat[15][15];
long long save[1<<14];
long long s2[500];
long long all[1<<14];int lowbit(int x)
{return x&(-x);
}void test()
{int cnt=0;for(int i=0;i<(1<<14);i++){for(int j=i;j>0;j=(j-1)&i){cnt++;}}cout<<cnt<<endl;cout<<(1<<28)<<endl;
}int main() {s2[0] = 1;for(int i=1;i <= 14*14;i++)s2[i] = (2*s2[i-1])%MOD;//test();int T;cin>>T;int tt=1;while(T--){int kk,n,m;scanf("%d%d%d",&n,&m,&kk);int cnt0=0;memset(mat,0,sizeof(mat));for(int i=0;i<m;i++){int a,b;scanf("%d%d",&a,&b);a--; b--;if(a==b) cnt0++;else{mat[a][b] = mat[b][a] = 1;}}memset(save,0,sizeof(save));memset(all,0,sizeof(all));memset(dp,0,sizeof(dp));for(int i=0;i<(1<<n);i++){int tcnt=0;for(int j=0;j<n;j++){if( ((1<<j)&i) !=0){for(int k=j+1;k<n;k++){if( ((1<<k)&i) !=0 ){tcnt += mat[j][k];}}}}all[i] = s2[tcnt];}save[0] = 1;for(int i=1;i<(1<<n);i++){int ti = i-lowbit(i);int j = ti;long long tmp=0;for(;j>0;j=(j-1)&ti){tmp += save[i-j]*all[j];tmp %= MOD;}save[i] = (all[i]-tmp+MOD)%MOD;dp[0][i] = save[i];}for(int i=1;i<kk;i++){for(int j=1;j<(1<<n);j++){int tj= j-lowbit(j);for(int k=tj; k>0;k = (k-1)&tj ){dp[i][j] += dp[i-1][k]*save[j-k];dp[i][j] %= MOD;}}}printf("Case #%d:\n",tt++);cout<<dp[kk-1][(1<<n)-1]*s2[cnt0]%MOD<<endl;}return 0;
}