Uva 1220 Party at Hali-Bula（最大独立子集问题）-白红宇的个人博客

Uva 1220 Party at Hali-Bula（最大独立子集问题）

发布日期：2021-05-14 14:38:04 浏览次数：22 分类：精选文章

本文共 1593 字，大约阅读时间需要 5 分钟。

题目大意：

给一个图，要求相邻节点不能同时选择，求最多能选出多少个节点，其次，判断最大节点数的情况是否唯一。

思路：

即求最大独立子集。在此基础上再判断情况唯一就行。

反思：

起初写了一个暴力判断情况唯一的，再一个节点下枚举判断每一个子节点是否情况唯一。这个代码再poj和hdoj上都过了，再uva上超时了，索性照着紫书上的方法再开一个vis数组再做一次dp。紫书开了一个二维数组a[i][0/1]来表示i节点选或不选得到的结果。如果不开二维数组的话，也可以开两个数组s[i]，gs[i]，分别记录子节点的答案和孙子节点的答案，同时需要开一个f[i]数组来记录i节点的父节点，稍显繁琐。本着简洁清楚的原则至上，开一个二维数组更好维护。就思路而言，如果判断一个题目是最大独立集问题，那么每个点有两个最基本的状态，即选或者不选，同时维护一些信息。

代码（暴力判断唯一性）

#include
   
    #include
    
     #include
     #include
      
       #include
       
        #include
        
         using namespace std;const int MAXN=200;map
         
           m;vector
          
            v[MAXN+5];char name[MAXN+5],na[MAXN+5];//string name,na;int n,d[MAXN+5],s[MAXN+5],gs[MAXN+5],f[MAXN+5];bool vis[MAXN+5];bool ans=0;void dfs(int now,int fa){ f[now]=fa; for(int i=0;i
           
            gs[now]+1){ l=v[now].size(); for(int i=0;i
            
             >name>>na; if(!m.count(name))m[name]=cnt++; if(!m.count(na))m[na]=cnt++; v[m[na]].push_back(m[name]); } dfs(1,0); printf("%d ",d[1]); if(vis[1]) printf("No\n"); else printf("Yes\n"); for(int i=0;i<=n;i++){ d[i]=0;s[i]=0;gs[i]=0;f[i]=0; vis[i]=0; v[i].clear(); } m.clear(); }}

代码（dp判断唯一性）

#include
   
    #include
    #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;vector
         
           v[210];map
          
            m;char a[210],b[210];int ans[210][2];bool vis[210][2];void dfs(int now){ ans[now][1]=1; for(int i=0;i
           
            ans[s][0])vis[now][0]|=vis[s][1]; else if(ans[s][0]>ans[s][1])vis[now][0]|=vis[s][0]; }}int main(){ int t,cnt; while(~scanf("%d",&t)&&t){ scanf("%s",a); cnt=1; m[a]=cnt++; for(int i=1;i
            
             ans[1][1]){ if(vis[1][0]) puts("No"); else puts("Yes"); } else if(ans[1][0]

上一篇：requests库-爬虫必备-请求方法与响应内容

下一篇：HDU 2102 A计划（BFS+细节维护）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题目大意：

思路：

反思：

代码（暴力判断唯一性）

代码（dp判断唯一性）

发表评论

最新留言

关于作者

推荐文章