第8个点为什么会T
查看原帖
第8个点为什么会T
194093
天梦楼主2021/3/5 21:28
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<deque>
#include<cstdlib>
#include<ctime>
#define dd double
#define ld long double
#define ll long long
#define ull unsigned long long
#define N 501
#define M 300501
using namespace std;

int n,m,a[N][N];
int read(){
	int x=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return x;
}

struct DLX{

	struct rode{
		int l,r,up,down,c,ro;
	};
	rode p[M];//0 head  1-n c  n+1 1
	int head,ans[M],tail;
	int lie[M],row[M],lienum[M];

	void init(){
//		p[0].l=m;p[0].r=1;
//		for(int i=1;i<=m;i++) p[i].l=i-1,p[i].r=i+1,p[i].c=i;
//		p[m].r=0;tail=m;
		for(int i=0;i<=m;i++){
			p[i].r=i+1;
			p[i].l=i-1;
//			p[i].up=p[i].down=i;
			p[i].c=i;
		}
		p[m].r=0;p[0].l=m;tail=m;
		for(int i=1;i<=m;i++) lie[i]=i;
		for(int i=1;i<=n;i++){
			int first=tail+1;
			for(int j=1;j<=m;j++){
				int x=read();
				if(x){
					lienum[j]++;
					p[++tail].up=lie[j];p[lie[j]].down=tail;lie[j]=tail;
					p[tail].l=tail-1;p[tail].r=tail+1;p[tail].down=j;
					p[tail].c=j;p[tail].ro=i;
					if(!row[i]) row[i]=tail;
				}
			}
				
			p[first].l=tail;p[tail].r=first;
		}
		for(int i=1;i<=m;i++) p[i].up=lie[i];
	}
	
	void sign(int num){
		int lien=p[num].c;
		p[p[lien].l].r=p[lien].r;
		p[p[lien].r].l=p[lien].l;
		for(int k=p[lien].down;k!=lien;k=p[k].down)
			for(int j=p[k].r;j!=k;j=p[j].r){
				p[p[j].down].up=p[j].up;
				p[p[j].up].down=p[j].down;
			}
	}
	
	void unsign(int num){
		int lien=p[num].c;
		for(int k=p[lien].up;k!=lien;k=p[k].up)
			for(int j=p[k].l;j!=k;j=p[j].l){
				p[p[j].down].up=j;
				p[p[j].up].down=j;
			}
		p[p[lien].l].r=lien;
		p[p[lien].r].l=lien;
	}
	
	bool dfs(){
		int now=p[0].r;
		if(p[0].r==0) return 1;
		for(int i=p[0].r;i!=0;i=p[i].r) if(lienum[now]>lienum[i]) now=i;
		sign(now);
		for(int k=p[now].down;k!=now;k=p[k].down){
			//choose k
			for(int j=p[k].r;j!=k;j=p[j].r)
				sign(j);
			ans[++head]=p[k].ro;
			if(dfs()) return 1;
			head--;
			for(int j=p[k].l;j!=k;j=p[j].l)
				unsign(j);
		}
		unsign(now);
		return 0;
	}
};
DLX dlx;

int main(){
	n=read();m=read();
	dlx.init();
	if(dlx.dfs())
		for(int i=1;i<=dlx.head;i++) printf("%d ",dlx.ans[i]);
	else printf("No Solution!\n");
	return 0;
}
2021/3/5 21:28
加载中...