HDU 3091 Necklace (状态压缩dp) - dblank

HDU 3091 Necklace (状态压缩dp)

Necklace

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 327680/327680 K (Java/Others)
Total Submission(s): 658    Accepted Submission(s): 217

Problem Description
One day , Partychen gets several beads , he wants to make these beads a necklace . But not every beads can link to each other, every bead should link to some particular bead(s). Now , Partychen wants to know how many kinds of necklace he can make.

 

Input
It consists of multi-case .
Every case start with two integers N,M ( 1<=N<=18,M<=N*N )
The followed M lines contains two integers a,b ( 1<=a,b<=N ) which means the ath bead and the bth bead are able to be linked.

 

Output
An integer , which means the number of kinds that the necklace could be.

 

Sample Input
3 3 1 2 1 3 2 3

 

Sample Output
2

 

Source
题意:给你一些珠子,这些珠子有编号,然后给可以相邻的珠子的编号,把他们全部串起来有多少种方案。状态压缩,dp(i, j),i表示当前集合状态为i最后一个为j的方案数,由于有重复的,我们固定起点为1的方案数,然后枚举其他不在当前集合的珠子状态转移,不过按照样例,1-2-3-1,和1-3-2-1是不同的情况。
#include<iostream>  
#include<cstdio>  
#include<algorithm>  
#include<map>  
#include<cstring>  
#include<map>  
#include<set>  
#include<queue>  
#include<stack>  
using namespace std;  
const int N = (1<<18) + 10;  
const double eps = 1e-10;  
typedef long long ll;  
ll dp[N][20];  
int Map[20][20];  
int main()  
{  
    int n, m;  
    while(~scanf("%d%d", &n, &m))  
    {  
        memset(Map, 0, sizeof(Map));  
        memset(dp, 0, sizeof(dp));  
        int u, v;  
        while(m--)  
        {  
            scanf("%d%d", &u, &v);  
            Map[u][v] = Map[v][u] = 1;  
        }  
        dp[1][1] = 1;  
        int num = (1<<n) - 1;  
        for(int i = 1; i<=num; i++)  
        {  
            for(int j = 1; j<=n; j++)  
            {  
                if(!dp[i][j])  
                    continue;  
                for(int k = 1; k<=n; k++)  
                {  
                    if(!Map[j][k] || (i & (1<<(k-1))) || !(i & (1<<(j-1))))  
                        continue;  
                    dp[i|(1<<(k-1))][k] += dp[i][j];  
                }  
            }  
        }  
        ll ans = 0;  
        for(int i = 1; i<=n; i++)  
            if(Map[1][i])  
                ans += dp[num][i];  
        cout<<ans<<endl;  
    }  
    return 0;  
}

 

相关文章

发表新评论