旅行

旅行

这道题再次发扬了noip看范围过数据（ 骗分）的风范 对于前`的数据可以适用于瞎搞的数据结构加上一个贪心dfs轻松水过

#include<bits/stdc++.h> using namespace std; int m,n; int vis[5002]; int u,v; struct node { int totl;//数量 int reach_[5001];//接通点 }a[5001]; void dfs(int nowl) { sort(a[nowl].reach_+1,a[nowl].reach_+a[nowl].totl+1); for(int i=1;i<=a[nowl].totl;++i) { if(!vis[a[nowl].reach_[i]]) { vis[a[nowl].reach_[i]]=1; cout<<a[nowl].reach_[i]<<" "; dfs(a[nowl].reach_[i]); } } } int main() { cin>>n>>m; if(m==n-1) { for(int i=1;i<=m;++i) { cin>>u>>v; a[u].reach_[++a[u].totl]=v; a[v].reach_[++a[v].totl]=u; } cout<<"1 "; vis[1]=1; dfs(1); } }

嗯…nice~ 对于临接链表在这里存图非常不爽 由于你需要使用sort对当前节点进行处理，使用贪心（走最小字典序） 所以你需要再开一个数组进行存入以便于排序，那么这个数组就显得至关重要，数组开大了就TLE，而且也不能太小，所以我们就尝试去开成50左右，至少不会超时间 （但别人想卡死你那就没招了）由于不太会用vector之类的矩阵存图我还是用邻接链表； 同时给大家安利一波register int； 这个手动优化可以加快for循环的速度； 对于测试数据最后一个点大概快了100ms左右； 下面进入正题… 操作前看一波数据范围n==m； 基环树！！！ 对于这种数据结构第一件事就是找环； 之后就是依次断开所有的链去暴搜； 代码如下

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define rei register int using namespace std; int n,m;int stack[50001];int dfn[50001]; int ans[50001],top;int times,cnt,stop,flag; int tot,head[50001];int dad[50001]; struct node { int ver; int next; }edge[50001]; bool cmp(int x,int y) { return x<y; } inline void add(int x,int y) { edge[++tot].next=head[x]; edge[tot].ver=y; head[x]=tot; } inline void dfs1(int x,int fa) { ans[++top]=x; int vis[55];memset(vis,0,sizeof(vis)); int num=0; for(rei i=head[x];i;i=edge[i].next) { int y=edge[i].ver; if(fa==y) continue; vis[++num]=y; } sort(vis+1,vis+num+1,cmp); for(rei i=1;i<=num;++i) dfs1(vis[i],x); } inline void find_loop(int x) { dfn[x]=++times; for(rei i=head[x];i;i=edge[i].next) { int y=edge[i].ver; if(y==dad[x]) continue; if(dfn[y]) { if(dfn[y]<dfn[x]) continue; stack[++cnt]=y; for(;y!=x;y=dad[y]) stack[++cnt]=dad[y]; } else dad[y]=x,find_loop(y); } } inline void dfs2(int x,int fa,int ban1,int ban2) { if(stop) return; top++; if(x<ans[top]) flag=1; if(x>ans[top]&&!flag) { stop=1;return ;}//剪枝如果本次dfs所确定的顺序大于之前的直接return if(flag) ans[top]=x; int vis[55],num=0,ban=0; memset(vis,0,sizeof(vis)); //下面是枚举断链的精髓 if(x==ban1) ban=ban2; else if(x==ban2) ban=ban1; for(rei i=head[x];i;i=edge[i].next) { int y=edge[i].ver; if(y==fa) continue; if(y!=ban) vis[++num]=y; } sort(vis+1,vis+num+1,cmp); for(rei i=1;i<=num;++i) dfs2(vis[i],x,ban1,ban2); } int main() { cin>>n>>m; int u,v; for(int i=1;i<=m;++i) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } if(m==n-1) { dfs1(1,0); for(int i=1;i<=n;++i) cout<<ans[i]<<" "; } if(n==m) { int vis[5001];memset(vis,0,sizeof(vis)); memset(ans,0x3f,sizeof(ans));//初始化 find_loop(1); for(rei i=1;i<cnt;++i) { flag=top=stop=0; dfs2(1,1,stack[i],stack[i+1]); } for(rei i=1;i<=n;++i) cout<<ans[i]<<" "; } return 0; }

PS：第一次写题解and本题代码思路有对别人的借鉴； 我希望在细节上对大家有帮助