题意：多组数据，每组数据给你几行数，要求选出当中几行。使得每一列都有且仅有一个1。询问是可不可行，或者说能不能找出来。

题解：1、暴搜。2、DLX（Dancing links）。

本文写的是DLX。

算法參考白书P406或者http://www.cnblogs.com/grenet/p/3145800.html

我说一些仔细的东西，就是删除操作的形状是

|

——|————

——|————

——|————

被删除的点们之间的联系不用删，能够保留。准确地说它并非删去了这些点，而是删去这个形。

并且恢复时要反着恢复。

首先先确定从哪一列删除，进行一次remove，然后枚举这一列的每一行。对其进行remove。然后dfs，然后再resume。

跳出循环时再resume确定列。

附代码，应该非常好看，仅仅要略耐心 一点点点点点。。

我保证绝对照网上其它人的可读性强。

哦，对了。并不须要写点、行、列的单独的remove和resume函数。那太傻了，写模板也不须要，我想这应该永远用不上的。。。。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 400

#define NN 10000

using namespace std;

struct DLX

{

	int U[NN],D[NN],L[NN],R[NN],C[NN];

	int H[NN],T[NN],cnt;

	inline void init(int m)

	{

		cnt=0;

		memset(H,0,sizeof(H));

		for(cnt=0;cnt<=m;cnt++)

		{

			U[cnt]=D[cnt]=C[cnt]=cnt;

			L[cnt]=cnt-1,R[cnt]=cnt+1;

		}

		L[0]=--cnt,R[cnt]=0;

	}

	inline void newnode(int x,int y)

	{

		C[++cnt]=y;T[y]++;

		if(!H[x])H[x]=L[cnt]=R[cnt]=cnt;

		else L[cnt]=H[x],R[cnt]=R[H[x]];

		R[H[x]]=L[R[H[x]]]=cnt,H[x]=cnt;

		U[cnt]=U[y],D[cnt]=y;

		U[y]=D[U[y]]=cnt;

	}

	inline void scan(int n,int m)

	{

		int i,j,k;

		for(i=1;i<=n;i++)for(j=1;j<=m;j++)

		{

			scanf("%d",&k);

			if(k)newnode(i,j);

		}

	}

	inline void remove(int x)

	{

		for(int i=D[x];i!=x;i=D[i])

		{

			for(int j=R[i];j!=i;j=R[j])

			{

				U[D[j]]=U[j];

				D[U[j]]=D[j];

				T[C[j]]--;

			}

		}

		L[R[x]]=L[x];

		R[L[x]]=R[x];

	}

	inline void resume(int x)

	{

		for(int i=U[x];i!=x;i=U[i])

		{

			for(int j=L[i];j!=i;j=L[j])

			{

				U[D[j]]=j;

				D[U[j]]=j;

				T[C[j]]++;

			}

		}

		L[R[x]]=x;

		R[L[x]]=x;

	}

	inline bool dfs()

	{

		if(!R[0])return true;

		int S=R[0],W=T[S],i,j;

		for(i=R[S];i;i=R[i])if(T[i]<W)

		{

			W=T[i];

			S=i;

		}

		remove(S);

		for(i=D[S];i!=S;i=D[i])

		{

			for(j=R[i];j!=i;j=R[j])remove(C[j]);

			if(dfs())return true;

			for(j=L[i];j!=i;j=L[j])resume(C[j]);

		}

		resume(S);

		return false;

	}

}dlx;

int main()

{

//	freopen("test.in","r",stdin);

//	freopen("my.out","w",stdout);

	int n,m;

	while(~scanf("%d%d",&n,&m))

	{

		dlx.init(m);

		dlx.scan(n,m);

		if(dlx.dfs())puts("Yes, I found it");

		else puts("It is impossible");

	}

	return 0;

}

给点福利。

专属那些输出调试者。

	inline void print_line(int x)

	{

		int i=x;

		do{

			printf("%d->",i);

			i=R[i];

		}while(i!=x);

		puts("");

	}

	inline void print_list(int x)

	{

		int i=x;

		do{

			printf("%d->",i);

			i=D[i];

		}while(i!=x);

		puts("");

	}

	inline void print(int x)

	{

		int i=x;

		do{

			print_list(i);

			puts("|");

			i=R[i];

		}while(i!=x);

		puts("");

		puts("");

	}

当然。你非得点行列写单独操作我也不拦你。

        inline void remove_point(int x)

	{

		D[U[x]]=D[x];

		U[D[x]]=U[x];

		R[L[x]]=R[x];

		L[R[x]]=L[x];

	}

	inline void resume_point(int x)

	{

		D[U[x]]=x;

		U[D[x]]=x;

		R[L[x]]=x;

		L[R[x]]=x;

	}

	inline void remove_line(int x)

	{

		int i=x;

		do{

			U[D[i]]=U[i];

			D[U[i]]=D[i];

			i=R[i];

		}while(i!=x);

	}

	inline void resume_line(int x)

	{

		int i=x;

		do{

			U[D[i]]=i;

			D[U[i]]=i;

			i=L[i];

		}while(i!=x);

	}

	inline void remove_list(int x)

	{

		int i=x;

		do{

			R[L[i]]=R[i];

			L[R[i]]=L[i];

			i=D[i];

		}while(i!=x);

	}

	inline void resume_list(int x)

	{

		int i=x;

		do{

			R[L[i]]=i;

			L[R[i]]=i;

			i=U[i];

		}while(i!=x);

	}

然后数据我就不贴了，直接去看3740discuss吧，有两组。