救救孩子吧,2样例过不去求调
查看原帖
救救孩子吧,2样例过不去求调
587959
ydkxj楼主2025/1/16 19:24
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int l[100005],r[100005],u[100005],d[100005],ans[100005],h[1000005],s[1000005];
int row[1000005],cl[1000005],cnt=0,n,m;
void init(int x){
	for(int i=0;i<=x;i++){
		r[i]=i+1;
		l[i]=i-1;
		u[i]=d[i]=i;
	}
	r[x]=0,l[0]=x;
	memset(h,-1,sizeof h);
	memset(s,0,sizeof s);
	cnt=x+1;
}
void link(int x,int y){
	s[y]++;
	row[cnt]=x;
	cl[cnt]=y;
	r[cnt]=y;
	d[cnt]=d[y];
	u[d[y]]=cnt;
	d[y]=cnt;
	if(h[x]==-1)h[x]=r[cnt]=l[cnt]=cnt;
	else {
		r[cnt]=h[x];
		l[cnt]=l[h[x]];
		r[l[h[x]]]=cnt;
		l[h[x]]=cnt;	
	}
	cnt++;
	return;
}
void remove(int c){
			cout<<1145141;
	r[l[c]]=r[c],l[r[c]]=l[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[cl[j]]--;
		}
	}
}
void resume(int c){
//			cout<<1145140;
	for(int i=u[c];i!=c;i=u[i]){
		for(int j=l[i];j!=i;j=l[j]){
			u[d[j]]=j;
			d[u[j]]=j;
			s[cl[j]]++;
		}
	}
	l[r[c]]=r[l[c]]=c;
}
bool dance(int depth){
	if(r[0]==0){
		for(int i=0;i<depth;i++)cout<<ans[i]<<" ";
		return 1;
	}
	int c=r[0];
	for(int i=r[0];i!=0;i=r[i])if(s[i]<s[c])c=i;
	remove(c);
	for(int i=d[c];i!=c;i=d[i]){
		ans[depth]=row[i];
		for(int j=r[i];j!=i;j=r[j])remove(cl[j]);
		if(dance(depth+1))return 1;
		for(int j=l[i];j!=i;j=l[j])resume(cl[j]);
		cout<<1919;
	}
	resume(c);
	return 0;
}
int main(){
	cin>>n>>m;
	init(m);
	int f;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;++j){
			cin>>f;
			if(f)link(i,j);	
		}
	}
	if(!dance(0))cout<<"No Solution!";
	return 0;
} 
2025/1/16 19:24
加载中...