具体是根据OI Wiki上学的

#include<iostream>
#include<cstdio>
using namespace std;

const int MS =1000;
int ans,stk[MS];//记录答案

struct DLX
{

	int idx,first[MS],siz[MS];//idx:指针 first:行首指示 siz:每列元素个数
	int l[MS],r[MS],u[MS],d[MS];
	int col[MS],row[MS];//col:行 row:列
	
	void build(int n,int m)
	{
		int i;
		for(i=0;i<=m;i++)
		{
			l[i]=i-1; r[i]=i+1;
			u[i]=d[i]=i;
		}
		l[0]=m; r[m]=0; idx=m;
		memset(first, 0, sizeof(first));
		memset(siz, 0, sizeof(siz));
	}
	void insert(int rr,int c)
	{
		row[++idx]=rr; col[idx]=c; ++siz[c];
		u[idx]=c; d[idx]=d[c]; u[d[c]]=idx; d[c]=idx;

		if(first[rr]==0)
			first[rr]=l[idx]=r[idx]=idx;
		else
		{
			l[idx]=first[rr];
			r[idx]=r[first[rr]];
			l[r[first[rr]]]=idx;
			r[first[rr]]=idx;
		}
	}
	bool dance(int dep)
	{
		int i,j,c=r[0];
		if(r[0]==0)//空矩阵
		{
			ans=dep;
			return 1;
		}

		for(i=r[0];i!=0;i=r[i])
		 if(siz[i]<siz[c])
		  c=i;//查找元素最少的列
		
		remove(c);
		for(i=d[c];i!=c;i=d[i])
		{
			stk[dep]=row[i];//选择第i行
			for(j=r[i];j!=i;j=r[j])
			remove(col[j]);
			if(dance(dep+1)) return 1;
			for(j=l[i];j!=i;j=l[j])
			recover(col[j]);
		}
		recover(c);
		return 0;
	}
	void remove(int c)
	{
		int i,j;
		l[r[c]]=l[c]; r[l[c]]=r[c];
		for(i=d[c];i!=c;i=d[i])
		for(j=r[c];j!=c;j=r[j])
		{
			u[d[j]]=u[j]; d[u[j]]=d[j];
			--siz[col[j]];
		}
	}
	void recover(int c)
	{
		int i,j;
		l[r[c]]=r[l[c]]=c;
		for(i=u[c];i!=c;i=u[i])
		for(j=l[c];j!=c;j=l[j])
		{
			u[d[j]]=d[u[j]]=j;
			++siz[col[j]];
		}
	}
};

int main()
{
	DLX a;
	int n,m;
	int i,j;

	cin>>n>>m;
	a.build(n,m);
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	{
		int x;
		cin>>x;
		if(x) a.insert(i,j);
	}

	if(a.dance(1))
	{
		for(i=1;i<ans;i++)
		printf("%d ",stk[i]);
	}
	else
	printf("No Solution!");
	return 0;
}