hdoj 3957ダンスチェーン

一、アルゴリズムの参考資料:
ものが多すぎて、よく分かりません.翻訳された論文はmomodiの論文でいいです.直接リンクを貼ります.
1.dancing links(ダンスチェーン)参考資料:http://sqybi.com/
中のworksリンクにdx資料の圧縮カバンがあります.
2.momodiの論文:http://gaoyunxiang.com/wp-content/uploads/2010/02/Dancing_Links.pdf
3.011アリババプログラム設計公開試合の解題報告:http://www.notonlysuccess.com/?p=1062
まず自分でこのアルゴリズムを書いて、テンプレートを比較したほうがいいです.そうすると、効率の所在が分かります.
二、コード(見ないほうがいいです.バックアップ用だけで、長又は分かりにくいです.)
でも、小さいtrickyを使って、prepare()、結果は78 MSに走りました.
  

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
//freopen("data.in","r",stdin);
using namespace std;
#define MAXN 1000//
struct Node
{
	int x,y;
	int l,r,u,d;
	int s;
	Node(int ll,int rr,int uu,int dd,int xx,int yy){l=ll;r=rr;u=uu;d=dd;s=0;x=xx;y=yy;}
};
struct Table
{
	int h;//   
	vector<Node> v;
	//i:(i<<1,(i+n)<<1)// i                
	//bool f[N+1];//   i     2   
	//                       
	int n;//  
	int low,high;
	bool vis[MAXN];
	//  x      
	inline void delC(int x)
	{
		for(int i=v[x].d;i!=x;i=v[i].d)
		{
			v[v[i].l].r=v[i].r;
			v[v[i].r].l=v[i].l;
		}
	}
	
	inline void linkC(int x)
	{
		for(int i=v[x].u;i!=x;i=v[i].u)
		{
			v[v[i].r].l=i;
			v[v[i].l].r=i;
		}
	}
	
	inline void delR(int x)
	{
		for(int i=v[x].r;i!=x;i=v[i].r)
		{
			v[v[i].u].d=v[i].d;
			v[v[i].d].u=v[i].u;
			v[v[i].y].s--;
		}
	}
	inline void linkR(int x)
	{
		for(int i=v[x].l;i!=x;i=v[i].l)
		{
			v[v[i].u].d=i;
			v[v[i].d].u=i;
			v[v[i].y].s++;
		}
	}
	//cover
	//1.  x   
	//2.  <x1,x2,……>xi   
	//3.          （ ）
	//         
	inline void cover(int x)
	{
		delC(x);
		for(int i=v[x].r;i!=x;i=v[i].r)if(!v[i].s)delC(i);
		if(v[v[x].y^1].s)delR(v[x].x^1);//        
	}

	//resume
	//1.          （ ）
	//2.  <x1,x2,……>xi   
	//3.  x   
	inline void resume(int x)
	{
		if(v[v[x].y^1].s)linkR(v[x].x^1);	
		for(int i=v[x].l;i!=x;i=v[i].l)if(!v[i].s)linkC(i);
		linkC(x);
	}
	void init()
	{
		v.clear();
		//    ,    
		h=1;
		int i;
		for(i=0;i<=(n<<1|1);i++)v.push_back(Node(i,i,i,i,i,1));//2*n+2
		for(i=(n<<1)+2;i<(n<<2|2);i++)v.push_back(Node(i,i,i,i,0,i));//4*n+2
	}
	void linkHeader(int x,int y)
	{
		v[x].y=h;
		v[x].u=v[h].u;v[x].d=h;v[v[h].u].d=x;v[h].u=x;
		v[y].l=v[h].l;v[y].r=h;v[v[h].l].r=y;v[h].l=y;
		v[h].s++;//         ，     
	}
	
	void add(int x,int y)
	{
		v.push_back(Node(v[x].l,x,v[y].u,y,x,y));
		int cnt=v.size()-1;//  cnt push_back    
		v[v[x].l].r=cnt;v[x].l=cnt;v[x].s++;//           
		v[v[y].u].d=cnt;v[y].u=cnt;v[y].s++;
	}
	
	void build()
	{
		for(int i=1;i<=n;i++)
		{
			int m;
			scanf("%d",&m);
			int x1=i<<1,y1=(i+n)<<1;//
			linkHeader(x1,y1);
			add(x1,y1);//!!
			
			if(m==2)
			{
				int x2=x1|1,y2=y1|1;
				linkHeader(x2,y2);
				add(x1,y2);//!!0           
				add(x2,y1);
				add(x2,y2);
			}
			for(int j=0;j<m;j++)
			{
				int num,obj,model;
				scanf("%d",&num);
				for(int k=0;k<num;k++)
				{
					scanf("%d%d",&obj,&model);
					y1=( (obj+1+n)<<1 )|model;
					add(x1|j,y1);// x1    j      obj+1  model  
				}
			}
		}
	}
	int H()
	{
		memset(vis,0,sizeof(vis));
		int ret=0;
		for(int y=v[h].r;y!=h;y=v[y].r)
		{
			if(!vis[y])
			{
				ret++;vis[y]=true;
				for(int x=v[y].d;x!=y;x=v[x].d)
				{
					for(int z=v[x].r;z!=x;z=v[z].r)
						vis[v[z].y]=true;
				}
			}
		}
		return ret;
	}
	bool dfs(int step,int cur)
	{
		if(step+H()>cur)return false;
		if(v[h].r==h)return true;
		int ms=v[v[h].r].s,my=v[h].r;
		for(int y=v[h].r;y!=h;y=v[y].r)//       
		{
			if(ms>v[y].s)
			{
				ms=v[y].s;
				my=y;
			}
		}
		for(int x=v[my].d;x!=my;x=v[x].d)	//my   
		{
			cover(x);
			if(dfs(step+1,cur))
			{
				resume(x);
				return true;
			}
			resume(x);
		}
		return false;
	}
	bool prepare()
	{
		low=0;high=n;
		int pre=v[h].r,cur;
		for(cur=v[v[h].r].r;cur!=h;cur=v[cur].r)
		{
			bool c=( ((pre^1)!=cur)||((pre^1)==cur&&v[pre].s>2) );
			if(c&&v[cur].s==2)low++;
			pre=cur;
		}
		if(low==0)low=1;
		else high=n-1;

		int	defeat=1;//
		for(int x=v[h].d;x!=h;x=v[x].d)
		{
			int tmp=0;
			int y1=v[v[x].r].y;
			bool first=true;
			for(cur=v[v[x].r].r;cur!=x;cur=v[cur].r)
			{
				int y2=v[cur].y;
				bool c1=y2==(y1^1);
				bool c2=!c1&&v[y2^1].s==0;
				if(c1&&c2)tmp++;//
				if((y2&1)&&(!c1)&&v[y2^1].s>2&&first)
				{//    ，          
					first=false;
					tmp++;
				}
				y1=y2;
			}
			if(tmp>defeat)defeat=tmp;
		}
		int must=n-defeat+1;
		if(high>must)high=must;
		if(low==high)return true;
		return false;
	}
	
	int dlx()
	{
		scanf("%d",&n);
		init();		
		build();
	//	output(v.size());
		if(prepare())return low;
//		low=1;high=n;
		while(low<high)
		{
			int mid=(low+high)>>1;
			if(dfs(0,mid))high=mid;
			else low=mid+1;
		}
		return low;
	}
	void output(int cnt)
	{
		for(int i=1;i<cnt;i++)
		{
			//printf("%d %d %d %d
",i,v[i].x,v[i].y,v[i].s);
			printf("%d %d %d %d %d
",i,v[i].l,v[i].r,v[i].u,v[i].d);
		}
		cout<<endl;
	}
}G;
int main()
{
//	freopen("data.in","r",stdin);
	int T;
	cin>>T;
	int cases=1;
	while(T--)
	{
		printf("Case %d: %d
",cases++,G.dlx());
	}
	return 0;
}