欢迎来到Tyrue的博客
// #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;
}
标签:ch,Tyrue,int,博客,while,include
From: https://www.cnblogs.com/Tyrue-blog/p/16937338.html