Uoj 554 [unr 4] challenges Hamilton [find Hamilton path (adjustment method)]

Title Description

Link
Submit answer questions
Give a digraph , Find the longest path without passing through repeated points and edges , Ensure no double edge self ring .

Topic analysis

Look directly at Official explanation Slightly

After doing a little three staining so that there is no problem with the same color edge , We learned the posture of submitting answer questions ： Adjustment method , Find one that doesn't make the answer worse , And it can be adjusted all the time .（ If you enter a dead end, start again ）

On this question , Is to consider adding edges in random order , Then maintain a set of chains , Consider merging two chains at a time , Or replace an edge .

There are some problems in writing ：

• Violent judgment will form a ring version ：

  • It's very slow , Basically, I just finished one test . I found that I didn't judge whether the two points have penetration before walking / The degree of . It becomes very fast to go after judgment .
  • run 8,9 It took a long time to reach the point , The first 10 Points stuck 99996 perhaps 99997 I can't move . The discovery is the problem of random numbers , Directly in windows Next use srand(rand()) and random_shuffle(), In this way, there are only $2^{15}$ Sort by , It's strange to get out . The correct posture is to use c++11 Of mt19937 And the corresponding shuffle(…) The way , This loop section ( It is said that ) yes $2^{19937}-1$ Of .

• After the change, I still run slowly , So it's changed to LCT edition , But the speed difference is not too big , Running to 99996 After that, I still have to run for a long time (>10min) To get results . contrast The standard schedule of the author Later, I found that I used all the edges to judge every time , And the optimized scale is to compare those with those without entry / The relevant edges of the points of the degree are tested , In this way, when the chain length reaches 9999x Only constant edges need to be tested , Surprisingly fast .

So there are some conclusions ： If you run very slowly or are inefficient when submitting answers , Then there must be something wrong / There are some obvious optimizations that don't add , You can't just wait , Think about if there is anything you can improve . The general scale can be solved in a very short time .

in addition , The file opening method in the standard program is also worth learning ：

Finally, I put on the one that I didn't run fast Code：

#include<bits/stdc++.h>
#define maxn 100005
#define maxm 300005
using namespace std;
int n,m,id[maxm],X[maxm],Y[maxm],L[maxn],R[maxn];
bool use[maxm]; int cnt;
map<long long,int>edge;
namespace LCT{
    
    int ch[maxn][2],fa[maxn],sum[maxn],v[maxn];
    bool rev[maxn];
    #define il inline
    #define pa fa[x]
    il bool isc(int x){
    return ch[pa][1]==x;}
    il bool isr(int x){
    return ch[pa][0]!=x&&ch[pa][1]!=x;}
    il void pd(int x){
    
        if(rev[x]){
    
            swap(ch[x][0],ch[x][1]),rev[x]=0;
            if(ch[x][0]) rev[ch[x][0]]^=1;
            if(ch[x][1]) rev[ch[x][1]]^=1;
        }
    }
    il void pdpath(int x){
    if(!isr(x)) pdpath(pa);pd(x);}
    il void rot(int x){
    
        int y=fa[x],z=fa[y],c=isc(x);
        if(!isr(y)) ch[z][ch[z][1]==y]=x;
        (ch[y][c]=ch[x][!c])&&(fa[ch[y][c]]=y);
        fa[ch[x][!c]=y]=x,fa[x]=z;
    }
    il void splay(int x){
    
        pdpath(x);
        for(;!isr(x);rot(x))
            if(!isr(pa)) rot(isc(pa)==isc(x)?pa:x);
    }
    il void access(int x){
    
        for(int y=0;x;x=fa[y=x]) splay(x),ch[x][1]=y;
    }
    il void bert(int x){
    
        access(x),splay(x),rev[x]^=1;
    }
    il int sert(int x){
    
        access(x),splay(x);
        for(;ch[x][0];x=ch[x][0]);
        return x;
    }
    il void link(int x,int y){
    
        bert(x);
        fa[x]=y;
    }
    il void cut(int x,int y){
    
        bert(x),access(y),splay(y);
        fa[x]=ch[y][0]=0;
    }
	il bool check(int x,int y){
    bert(x); return sert(y)==x;}
}
using namespace LCT;
mt19937 rnd;
int main()
{
    
	freopen("hamil10.in","r",stdin);
	freopen("hamil10.out","w",stdout);
	srand(time(0));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=10;i++) scanf("%*d");
	for(int i=1;i<=m;i++) scanf("%d%d",&X[i],&Y[i]),id[i]=i,edge[1ll*X[i]*(n+1)+Y[i]]=i;
	for(;cnt<n-1;){
    
		cerr<<cnt<<endl;
		//srand(rand());
		shuffle(id+1,id+1+m,rnd);
		for(int o=1,i;o<=m&&cnt<n-1;o++) if(!use[i=id[o]]){
    
			int x=X[i],y=Y[i];
			//cerr<<x<<' '<<y<<endl;
			if(R[x]&&L[y]) continue;
			if(check(x,y)) continue;
			if(!R[x]&&!L[y]) use[i]=1,cnt++,R[x]=y,L[y]=x,link(x,y);
			else if(rand()&1){
    
				if(R[x]) L[R[x]]=0,cut(x,R[x]),use[edge[1ll*x*(n+1)+R[x]]]=0,cnt--;
				if(L[y]) R[L[y]]=0,cut(L[y],y),use[edge[1ll*L[y]*(n+1)+y]]=0,cnt--;
				use[i]=1,cnt++,R[x]=y,L[y]=x,link(x,y);
			}
		}
	}
	printf("%d\n",n);
	for(int i=1;i<=n;i++) if(!L[i]){
    
		for(int x=i;x;x=R[x]) printf("%d ",x);
		return 0;
	}
}