HDU 5823 color II

柔光的暖阳◎ 2022-09-25 11:26 29阅读 0赞

题目链接：  
[http://acm.split.hdu.edu.cn/showproblem.php?pid=5823][http_acm.split.hdu.edu.cn_showproblem.php_pid_5823]

题目大意：找出一个集合中每个子集包括它自己的的最少涂色数

解题思路：考虑到一个集合中颜色相等的点必定没有边相连，对于一个集合i，我们可以去除其中颜色相等点，再求剩下的点的最小染色数，答案就是剩下的点的最小染色数加1。  
具体做法就是预处理出所有没有边相连的点的集合，即独立的集合，对于一个集合i，枚举它的子集j，如果子集j是独立的，则可如下转移  
dp\[i\]=max(dp\[i\],dp\[i-j\]+1)

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <numeric>
    #include <functional>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    
    const int inf1=-1*1e9;
    double EPS=1e-10;
    typedef long long LL;
    
    LL  inf=1e9;
    int edge[25][25],dp[1<<18];
    int ju[1<<18];
    
    void ini()
    {
        LL t=1;
        for(int i=1; i<=32; i++)
        {
            t*=2;
        }
        inf=t;
    }
    int main()
    {
        ini();
        int T,n;
        RI(T);
        while(T--)
        {
            RI(n);
            memset(edge,0,sizeof(edge));
            memset(ju,0,sizeof(ju));
            for(int i=0; i<n; i++)
            {
                char ss[25];
                scanf("%s",ss);
                for(int j=0; j<n; j++)
                    edge[i][j]=ss[j]-'0';
            }
            int tot=1<<n;
    
            for(int i=1; i<tot; i++)
                for(int j=0; j<n; j++)
                {
                    if((i>>j)&1)
                    {
                        for(int k=0; k<n; k++)
                        {
                            if(((i>>k)&1)&&(edge[j][k]))
                            {
                                ju[i]=1;
                                break;
                            }
                        }
                    }
                    if(ju[i]==1) break;
                }
    
            for(int i=1; i<tot; i++)
            {
                if(!ju[i])
                {
                    dp[i]=1;
                    continue;
                }
                dp[i]=1000000000;
                for(int j=(i-1)&i; j; j=(j-1)&i)
                {
                    if(!ju[j]) dp[i]=min(dp[i],dp[i-j]+1);
                }
            }
            LL t=1,ans=0;
            for(int i=1; i<tot; i++)
            {
                t=t*233%inf;
                ans=(ans+(LL(dp[i])*t)%inf)%inf;
            }
            printf("%I64d\n",ans);
        }
        return 0;
    }

[http_acm.split.hdu.edu.cn_showproblem.php_pid_5823]: http://acm.split.hdu.edu.cn/showproblem.php?pid=5823