Partition Refinement

今天613问我怎么做DFA最小化..呃..这个我怎么可能会做呢..

于是我就去学习了一点姿势,先把我Partition Refinement Data Structure的代码发上来好了..

我挺菜的代码重构了好几遍才找到正确的写法..可能是因为文化课智商下降了

#include<bits/stdc++.h>

using namespace std;

struct q{

   vector<int>son;int tid;

   q(int sz=0):tid(-1){if(sz)son.resize(sz);}

};

typedef pair<int,int>o;

struct p{

   vector<q>z;

   vector<o>b;

   p(int t){

      z.emplace_back(t);

      b.resize(t+1);

      for(int i=0;i<t;++i)

         b[i+1]=o(0,i),z[0].son[i]=i+1;

   }

   void _reassign(q&a,int s){

      q&t=z[a.tid];

      int id=a.son[s];

      if(s!=a.son.size()-1){

         int idr=a.son[a.son.size()-1];

         b[idr].second=s;

         swap(a.son[s],a.son[a.son.size()-1]);

      }a.son.pop_back();

      b[id]=o(a.tid,t.son.size());

      t.son.push_back(id);

   }

   vector<o>split(vector<int>t){

      vector<o>q;

      for(int v:t){

         if(z[b[v].first].tid==-1){

            q.emplace_back(b[v].first,z.size());

            z[b[v].first].tid=z.size(),z.emplace_back();

         }_reassign(z[b[v].first],b[v].second);

      }for(o g:q)

         z[g.first].tid=-1;

      return q;

   }

   bool printset(q&e){

      if(e.son.size()){

         printf("{%d",e.son[0]);

         for(int i=1,_=e.son.size();i<_;++i)

            printf(",%d",e.son[i]);

         puts("}");return 0;

      }return 1;

   }

   void print(){

      puts("{");

      for(auto e:z)

         putchar('\t'),printset(e);

      puts("}");

   }

};

int main(){

   int n,m;scanf("%d %d",&n,&m);

   p zz(n);

   zz.print();

   while(m--){

      vector<int>ss;

      int u;while(scanf("%d",&u),u)ss.push_back(u);

      sort(ss.begin(),ss.end());

      ss.erase(unique(ss.begin(),ss.end()),ss.end());

      printf("Split with set(of size %zu):\n",ss.size());

      for(int i:ss)

         printf("%d ",i);

      puts("");

      auto q=zz.split(ss);

      puts("Splits out:{");

      for(auto i:q){

         puts("\t{");

         printf("\t\tDiv:"),zz.printset(zz.z[i.first ])?printf("\n"):0;

         printf("\t\tRem:"),zz.printset(zz.z[i.second])?printf("\n"):0;

         puts("\t}");

      }puts("}\nNow set is like:");

      zz.print();

   }return 0;

}

哈哈想不到吧博客园,你把tab强行定为4格(你这是会引起公愤的),但是老子会转空格!你怕了吧哈哈哈..

巴特西

Partition Refinement

最新文章

热门文章