[ACM] POJ 3740 Easy Finding （DLX模板题）

本文主要是介绍[ACM] POJ 3740 Easy Finding （DLX模板题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Input

Output

Sample Input

3 3
0 1 0
0 0 1
1 0 0
4 4
0 0 0 1
1 0 0 0
1 1 0 1
0 1 0 0

Sample Output

Yes, I found it
It is impossible

Source

 

解题思路：

题意为由01组成的矩阵，问能不能挑出几行使组成的新矩阵每列只有一个1.

套用Dlx模板，不过G++ 超时，C++勉强能过。

代码：

#include <iostream>
#include <stdio.h>
using namespace std;
const int maxnode=5000;
const int maxm=310;
const int maxn=18;struct DLX
{int n,m,size;int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode];int H[maxn];//行头节点int S[maxm];//每列有多少个节点int ansd,ans[maxn];//如果有答案，则选了ansd行，具体是哪几行放在ans[ ]数组里面，ans[0~ansd-1];void init(int _n,int _m){n=_n,m=_m;for(int i=0;i<=m;i++){S[i]=0;U[i]=D[i]=i;//初始状态下，上下自己指向自己L[i]=i-1;R[i]=i+1;}R[m]=0,L[0]=m;size=m;//编号，每列都有一个头节点，编号1-mfor(int i=1;i<=n;i++)H[i]=-1;//每一行的头节点}void link(int r,int c)//第r行，第c列{++S[Col[++size]=c];//第size个节点所在的列为c,当前列的节点数++Row[size]=r;//第size个节点行位置为rD[size]=D[c];//下面这四句头插法（图是倒着的？)U[D[c]]=size;U[size]=c;D[c]=size;if(H[r]<0)H[r]=L[size]=R[size]=size;else{R[size]=R[H[r]];L[R[H[r]]]=size;L[size]=H[r];R[H[r]]=size;}}void remove(int c)//删除节点c，以及c上下节点所在的行,每次调用这个函数，都是从列头节点开始向下删除，这里c也可以理解为第c列{                 //因为第c列的列头节点编号为cL[R[c]]=L[c];R[L[c]]=R[c];for(int i=D[c];i!=c;i=D[i])for(int j=R[i];j!=i;j=R[j]){U[D[j]]=U[j];D[U[j]]=D[j];--S[Col[j]];}}void resume(int c)//恢复节点c,以及c上下节点所在的行(同上，也可以理解为从第c列的头节点开始恢复{for(int i=U[c];i!=c;i=U[i])for(int j=L[i];j!=i;j=L[j])++S[Col[U[D[j]]=D[U[j]]=j]]; //打这一行太纠结了 T TL[R[c]]=R[L[c]]=c;}bool dance(int d)//递归深度{if(R[0]==0){ansd=d;return true;}int c=R[0];for(int i=R[0];i!=0;i=R[i])if(S[i]<S[c])c=i;remove(c);//找到节点数最少的列，当前元素不是原图上0，1的节点，而是列头节点for(int i=D[c];i!=c;i=D[i]){ans[d]=Row[i];//列头节点下面的一个节点for(int j=R[i];j!=i;j=R[j])remove(Col[j]);if(dance(d+1))//找到，返回return true;for(int j=L[i];j!=i;j=L[j])resume(Col[j]);}resume(c);return false;}
};DLX x;
int n,m;int main()
{while(scanf("%d%d",&n,&m)!=EOF){x.init(n,m);int num;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>num;if(num)x.link(i,j);}}if(!x.dance(0))printf("It is impossible\n");elseprintf("Yes, I found it\n");}return 0;
}

 

这篇关于[ACM] POJ 3740 Easy Finding （DLX模板题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---