hihocoder1317 :搜索四·跳舞链

精确覆盖问题是指对于给定的一个由0-1组成的矩阵，是否能找到一个行的集合，使得集合中每一列都恰好包含一个1。

//Achen
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<queue>
#include<ctime>
#include<cmath>
const int N=10517;
typedef long long LL;
using namespace std;
int T,n,m,s[N],l[N],r[N],up[N],dn[N],fir[N],xx[N],yy[N],head,tot;

template<typename T> void read(T &x) {
    char ch=getchar(); x=0; T f=1;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
}

void clear() {
    tot=m;
    for(int i=0;i<=m;i++) {
        s[i]=0;
        l[i]=i-1; 
        r[i]=i+1;
        dn[i]=up[i]=i;
    }
    r[m]=head; l[head]=m;
    for(int i=1;i<=n;i++) fir[i]=-1;   
}

void add(int x,int y,int id) {
    xx[id]=x;
    yy[id]=y;
    dn[id]=dn[y];
    up[dn[y]]=id;
    dn[y]=id;
    up[id]=y;
    s[y]++;
    if(fir[x]==-1) fir[x]=l[id]=r[id]=id;
    else {
        r[id]=fir[x];
        l[id]=l[fir[x]];
        r[l[id]]=id;
        l[fir[x]]=id;
    }
}

void resume(int k) {
    for(int i=dn[k];i!=k;i=dn[i]) {
        for(int j=r[i];j!=i;j=r[j]) {
            dn[up[j]]=up[dn[j]]=j;
            ++s[yy[k]];
        }
    } 
    l[r[k]]=r[l[k]]=k;
}

void remove(int k) {
    l[r[k]]=l[k];
    r[l[k]]=r[k];
    for(int i=dn[k];i!=k;i=dn[i]) {
        for(int j=r[i];j!=i;j=r[j]) {
            up[dn[j]]=up[j];
            dn[up[j]]=dn[j];
            --s[yy[j]];
        }
    }    
}

int dance() {
    if(r[head]==head) return 1;
    int k=r[head];
    for(int i=r[head];i!=head;i=r[i]) 
        if(s[i]<s[k]) k=i;
    remove(k);
    for(int i=dn[k];i!=k;i=dn[i]) {
        for(int j=r[i];j!=i;j=r[j]) remove(yy[j]);
        if(dance()) return 1;
        for(int j=r[i];j!=i;j=r[j]) resume(yy[j]); 
    }
    resume(k);
    return 0;
}

void init() {
    read(T);
    while(T--) {
        read(n); read(m);
        clear();
        int f;
        for(int i=1;i<=n;i++) 
            for(int j=1;j<=m;j++) {
                read(f);
                if(f) add(i,j,++tot);
            }
        if(dance()) printf("Yes
");
        else printf("No
");
    }
}

int main() {
#ifdef DEBUG
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    init();
    return 0;
}