#554. 【UNR #4】挑战哈密顿

题目描述

题解

第一道玩出来的提答题

数据特殊在于生成方式，是一条链上面随机加边（虽说没什么卵用）

手玩可以玩出点1，纯暴力可以跑出点2,3+4~9的1分

xjb剪枝可以得到40~60不等的分数，以上做法均未写过

神必做法：

首先一个显然是假的做法，每次把两条链首位相接，最后接到只有一条链，然后连点3都跑不出来

修改一下，如果一条链接到了另一条链的中间，那么就把被接的链断开接上去，类似access操作

然后直接艹过了前9个点，主要是因为图比较稀疏，所以效果极佳

第十个点跑不动了，用一开始的暴力水了1分就结束了

比赛结束之后用上面的做法尝试跑第10个点，跑了0.5h后到3就卡住了，之后吃了个饭回来就跑完了

数字是剩余链数，跑了1.5h

code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define sqr(x) ((x)*(x))
#define ll long long
#define file
using namespace std;

int a[500001][2],ls[500001],b[500001],d[500001],A[11],Len[500001],pre[500001],nx[500001],n,m,i,j,k,l,len,t,x,tot,Ls;

void New(int x,int y) {++len;a[len][0]=y;a[len][1]=ls[x];ls[x]=len;}
int random(int x,int y) {return (1ll*rand()*23333+rand())%(y-x+1)+x;}
void dg(int t) {if (pre[t]) dg(pre[t]); printf("%d ",t);}
int gf(int t) {if (!nx[t]) return t;return gf(nx[t]);}

int main()
{
	l=time(NULL);
	srand(l);
	#ifdef file
	freopen("hamil10.in","r",stdin);
	#endif
	
	scanf("%d%d",&n,&m);
	fo(i,1,10) scanf("%d",&A[i]);
	fo(i,1,m) scanf("%d%d",&j,&k),New(j,k);
	
	t=n;
	fo(i,1,n) d[i]=i,Len[i]=1;
	while (t>1)
	{
		l=random(1,t);
		x=d[l];
		tot=0;
		for (i=ls[x]; i; i=a[i][1])
//		if (Len[a[i][0]]-1<Len[x] && gf(a[i][0])!=x)
		if (gf(a[i][0])!=x)
		b[++tot]=i;
		
		if (tot)
		{
			i=b[random(1,tot)];
			if (Len[a[i][0]]==1)
			{
//				cout<<x<<" "<<a[i][0]<<endl;
				d[l]=d[t--];
				nx[x]=a[i][0],pre[a[i][0]]=x;
			}
			else
			{
				k=pre[a[i][0]];
				nx[pre[a[i][0]]]=0;
				pre[a[i][0]]=x;nx[x]=a[i][0];
//				cout<<x<<" "<<a[i][0]<<endl;
				d[l]=k;
			}
			while (nx[x]) Len[nx[x]]=Len[x]+1,x=nx[x];
		}
		if (t!=Ls)
		cout<<t<<endl,Ls=t;
	}
	
	freopen("hamil10.out","w",stdout);
	l=0;
	fo(i,1,t) if (Len[d[i]]>l) l=Len[d[i]],k=d[i];
	printf("%d
",l);
	dg(k);
}