0x20 搜索-白红宇

0x20 搜索

阅读量：5291 次

发布时间：2019-06-14

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

这里基本就是入门吧。

可达性统计用bitset搞的判重，发现这东西是真好用哈，空间还小

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              using namespace std;map
              
               mp[31000];struct node{ int x,y,next;}a[31000];int len,last[31000];void ins(int x,int y){ len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len;}int top,sta[31000];int ru[31000];bitset<30010>s[31000];int main(){ int n,m; scanf("%d%d",&n,&m); len=0;memset(last,0,sizeof(last)); memset(ru,0,sizeof(ru)); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); if(mp[x][y]==false) { ins(y,x);ru[x]++; mp[x][y]=true; } } top=0; for(int i=1;i<=n;i++) { if(ru[i]==0)sta[++top]=i; s[i][i]=1; } while(top!=0) { int x=sta[top];top--; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; ru[y]--;s[y]|=s[x]; if(ru[y]==0) sta[++top]=y; } } for(int i=1;i<=n;i++)printf("%d\n",s[i].count()); return 0;}

可达性统计

小猫爬山就冲着Freda和rainbow这口狗粮随便写了。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              using namespace std;int n,W,mmin;int c[20],d[20];void dfs(int k,int sp){ if(sp>=mmin)return ; if(k==n+1) { mmin=sp; return ; } for(int i=1;i<=sp;i++) if(d[i]+c[k]<=W) { d[i]+=c[k]; dfs(k+1,sp); d[i]-=c[k]; } d[sp+1]=c[k]; dfs(k+1,sp+1);}int main(){ scanf("%d%d",&n,&W); for(int i=1;i<=n;i++)scanf("%d",&c[i]); d[1]=0;mmin=n;dfs(1,1); printf("%d\n",mmin); return 0;}