Tyrue的博客()-其他

Tyrue的博客()

欢迎来到Tyrue的博客

Luogu_Blog

// #Tyrue#
#include<map>
#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
const int N=6e3+10;
struct Node{
    int l,r,u,d,ro,c;
}node[N];
int T,n,m,cnt;
int row[N],ans[N],lcnt[N];
void init(){    
    for(int i=0;i<=m;i++){
        node[i].u=i;
        node[i].d=i;
        node[i].l=i-1;
        node[i].r=i+1;
    }
    node[0].l=m;
    node[m].r=0;
    cnt=m;
    return ;
}
void add(int x,int y){
    // node[++cnt]=((Node){0,0,node[x].u,y,x,y});
    node[++cnt].ro=x;
    node[cnt].c=y;
    node[cnt].u=node[y].u;
    node[cnt].d=y;
    node[node[cnt].u].d=cnt;
    node[y].u=cnt;
    if(!row[x]){
        node[cnt].l=cnt;
        node[cnt].r=cnt;
        row[x]=cnt;
    }else{
        node[cnt].l=node[row[x]].l;
        node[cnt].r=row[x];
        node[node[cnt].l].r=cnt;
        node[node[cnt].r].l=cnt;
    }
    lcnt[y]++;
    return ;
}
void remove(int x){
    for(int i=node[x].d;i!=x;i=node[i].d){
        for(int j=node[i].r;j!=i;j=node[j].r){
            node[node[j].d].u=node[j].u;
            node[node[j].u].d=node[j].d;
            lcnt[node[j].c]--;
        }
    }
    node[node[x].l].r=node[x].r;
    node[node[x].r].l=node[x].l;
}
void resume(int x){
    node[node[x].l].r=x;
    node[node[x].r].l=x;
    for(int i=node[x].d;i!=x;i=node[i].d){
        for(int j=node[i].r;j!=i;j=node[j].r){
            node[node[j].d].u=j;
            node[node[j].u].d=j;
            lcnt[node[j].c]++;
        }
    }
}
bool dance(int dep){
    if(node[0].r==0){
        // for(int i=1;i<dep;i++){
        //     printf("%d ",ans[i]);
        // }
        // puts("");
        for(int i=1;i<dep-1;i++){
            printf("%d ",ans[i]);
        }
        printf("%d\n",ans[dep-1]);
        return 1;
    }
    int C=node[0].r;
    for(int i=node[0].r;i;i=node[i].r){
        if(lcnt[i]<lcnt[C]){
            C=i;
        }
    }
    remove(C);
    for(int i=node[C].d;i!=C;i=node[i].d){
        ans[dep]=node[i].ro;
        for(int j=node[i].r;j!=i;j=node[j].r){
            remove(node[j].c);
        }
        if(dance(dep+1)){
            return 1;
        }
        for(int j=node[i].r;j!=i;j=node[j].r){
            resume(node[j].c);
        }
    }
    resume(C);
    return 0;
}
int main(){
    // T=read();
    n=read(),m=read();
    init();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int x=read();
            if(x){
                add(i,j);
            }
        }
    }
    if(!dance(1)){
        puts("No Solution!");
    }
    return 0;
}

欢迎来到Tyrue的博客

Luogu_Blog

// #Tyrue#
#include<map>
#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
const int N=6e3+10;
struct Node{
    int l,r,u,d,ro,c;
}node[N];
int T,n,m,cnt;
int row[N],ans[N],lcnt[N];
void init(){    
    for(int i=0;i<=m;i++){
        node[i].u=i;
        node[i].d=i;
        node[i].l=i-1;
        node[i].r=i+1;
    }
    node[0].l=m;
    node[m].r=0;
    cnt=m;
    return ;
}
void add(int x,int y){
    // node[++cnt]=((Node){0,0,node[x].u,y,x,y});
    node[++cnt].ro=x;
    node[cnt].c=y;
    node[cnt].u=node[y].u;
    node[cnt].d=y;
    node[node[cnt].u].d=cnt;
    node[y].u=cnt;
    if(!row[x]){
        node[cnt].l=cnt;
        node[cnt].r=cnt;
        row[x]=cnt;
    }else{
        node[cnt].l=node[row[x]].l;
        node[cnt].r=row[x];
        node[node[cnt].l].r=cnt;
        node[node[cnt].r].l=cnt;
    }
    lcnt[y]++;
    return ;
}
void remove(int x){
    for(int i=node[x].d;i!=x;i=node[i].d){
        for(int j=node[i].r;j!=i;j=node[j].r){
            node[node[j].d].u=node[j].u;
            node[node[j].u].d=node[j].d;
            lcnt[node[j].c]--;
        }
    }
    node[node[x].l].r=node[x].r;
    node[node[x].r].l=node[x].l;
}
void resume(int x){
    node[node[x].l].r=x;
    node[node[x].r].l=x;
    for(int i=node[x].d;i!=x;i=node[i].d){
        for(int j=node[i].r;j!=i;j=node[j].r){
            node[node[j].d].u=j;
            node[node[j].u].d=j;
            lcnt[node[j].c]++;
        }
    }
}
bool dance(int dep){
    if(node[0].r==0){
        // for(int i=1;i<dep;i++){
        //     printf("%d ",ans[i]);
        // }
        // puts("");
        for(int i=1;i<dep-1;i++){
            printf("%d ",ans[i]);
        }
        printf("%d\n",ans[dep-1]);
        return 1;
    }
    int C=node[0].r;
    for(int i=node[0].r;i;i=node[i].r){
        if(lcnt[i]<lcnt[C]){
            C=i;
        }
    }
    remove(C);
    for(int i=node[C].d;i!=C;i=node[i].d){
        ans[dep]=node[i].ro;
        for(int j=node[i].r;j!=i;j=node[j].r){
            remove(node[j].c);
        }
        if(dance(dep+1)){
            return 1;
        }
        for(int j=node[i].r;j!=i;j=node[j].r){
            resume(node[j].c);
        }
    }
    resume(C);
    return 0;
}
int main(){
    // T=read();
    n=read(),m=read();
    init();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int x=read();
            if(x){
                add(i,j);
            }
        }
    }
    if(!dance(1)){
        puts("No Solution!");
    }
    return 0;
}