【题解】2018NOIP 旅行

【NOIP2018】 旅行

• 60分
  dfs遍历一遍，优先考虑编号较小的点。
  （这一部分好像怎么样都可以水过去吧）

• 100分
  hmm，其实n^2暴力断边就可以了，但我（在hzj巨佬的帮助下）改了很久才改好（有三个点一直T）…

一开始我是这样写的

void dfs_2(int u)
{
    if((u>ans[tot+1][1])&&(!flag)) return;
    if(u<ans[tot+1][1]) flag=1;
    ans[++tot][0]=u; vis[u]=1;
    FOR(i,1,n) if(g[u][i]&&!vis[i]) dfs_1(i);
}

后来改成了这样

bool dfs_2(int u)
{
    if((u>ans[tot+1][1])&&(!flag)) return 0;
    if(u<ans[tot+1][1]) flag=1;
    ans[++tot][0]=u; vis[u]=1;
    FOR(i,1,n) if(g[u][i]&&!vis[i]) if(!dfs_2(i)) return 0;
    return 1;
}

为什么这样会快一些呢？
看这儿

if(!dfs_2(i)) return 0;

第二种写法的优秀之处在于：一发现当前情况没当前答案优，这整条线就“废了”；
而第一种写法如果发现当前情况没当前答案优，就会继续找它的“兄弟”。

好的就是这样：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define FOR(i,n,m) for(register int i=n;i<=m;++i)
using namespace std;

const int N=5010,INF=0x7fffffff;
int n,m,tot,t;
int ans[N][2];
bool g[N][N],vis[N],flag;
int x[N],y[N]; 

inline int read()
{
    int x=0; char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x;
}

void dfs_1(int u) {
    ans[++tot][0]=u; vis[u]=1;
    FOR(i,1,n) if(g[u][i]&&!vis[i]) dfs_1(i);
}

bool dfs_2(int u)
{
    if((u>ans[tot+1][1])&&(!flag)) return 0;
    if(u<ans[tot+1][1]) flag=1;
    ans[++tot][0]=u; vis[u]=1;
    FOR(i,1,n) if(g[u][i]&&!vis[i]) if(!dfs_2(i)) return 0;
    return 1;
}

int main()
{
    n=read(); m=read();
    FOR(i,1,n) ans[i][1]=INF;
    FOR(i,1,m)
    {
        x[i]=read(),y[i]=read();
        g[x[i]][y[i]]=g[y[i]][x[i]]=1;
    }
    if(m==n-1)
    {
    	dfs_1(1);
        FOR(i,1,n) printf("%d ",ans[i][0]);
	}
    else {
    	FOR(t,1,m) {
        int i=x[t],j=y[t];
        if(g[i][j])
        {
            memset(vis,0,sizeof(vis));
            tot=flag=0;//变量一定要记得清零啊 
            g[i][j]=g[j][i]=0;
            dfs_2(1);
            g[i][j]=g[j][i]=1;
            if(tot==n) FOR(k,1,n) ans[k][1]=ans[k][0];
        }
    }
    FOR(i,1,n) printf("%d ",ans[i][1]);
	} 
    return 0;
}

（虽然都说这道题比较水（确实），但本蒟蒻考试时爆零了，哎… ）