正題

評測記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=P5022

---

題目大意

一棵樹(可能是基環樹)，從1出發，每到達一個新的點就記錄下編號。求一種走法使得記錄下來的編號字典序最小。

---

解題思路

我們先不考慮基環樹。我們可以發現每次走字典序小的點就好了。我們可以排序一下就可以做到這點。
之后我們考慮基環樹，我們暴力刪邊將基環樹變為一棵普通的樹。然后計算答案。
時間復雜度:$O(n^2)$

---

code

#include<cstdio> #include<queue> #include<cstring> #include<algorithm> #define N 5010 using namespace std; struct node{int to,next; }a[2*N]; struct line{int x,y; }l[2*N]; int tot,n,m,t,ls[N],in[N],state[N],w[N],ans[N],x,y,q[N]; bool k[N][N],v[N]; void addl(int x,int y)//加邊 {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;in[y]++; } bool topsort(){int l=0,r=0;for (int i=1;i<=n;i++) if(in[i]==1) q[++r]=i;while(l<r) {int now=q[++l];for (int i=ls[now];i;i=a[i].next){int y=a[i].to;if(in[y]>1){in[y]--;if(in[y]==1) q[++r]=y;}}}if(r==n) return true;return false; }//拓撲求環 bool cmp(line x,line y) {return x.y>y.y;} void dfs(int x)//走一遍 {state[++t]=x;v[x]=true;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(k[x][y]||v[y]) continue;dfs(y);} } void check()//判斷是否為更小字典序 {int i;bool flag=false;for(i=1;i<=n;i++)if(state[i]<ans[i]){flag=true;break;}else if(state[i]>ans[i]) return;if(!flag) return;for(;i<=n;i++)ans[i]=state[i]; } void get_ans(int xs)//暴力刪邊 {int x=xs,b=0,i,last=0;do{w[++b]=x;in[x]=1;for(i=ls[x];i;i=a[i].next){int y=a[i].to;if(in[y]>1){x=y;break;}}}while(i);//記錄環的每個點w[++b]=xs;for(int i=1;i<b;i++)//枚舉刪除的邊{k[w[i]][w[i+1]]=k[w[i+1]][w[i]]=true;memset(v,0,sizeof(v));t=0;dfs(1);check();k[w[i]][w[i+1]]=k[w[i+1]][w[i]]=false;} } int main() {memset(ans,127/3,sizeof(ans));scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);l[i]=(line){x,y};l[i+m]=(line){y,x};}sort(l+1,l+1+2*m,cmp);//排序tot=1;for(int i=1;i<=2*m;i++)//加邊{addl(l[i].x,l[i].y);}if(m==n-1)//普通的樹{dfs(1);for(int i=1;i<=n;i++)printf("%d ",state[i]);return 0;}topsort();for(int i=1;i<=n;i++)if(in[i]>1){get_ans(i);break;}for(int i=1;i<=n;i++)printf("%d ",ans[i]); }

總結

以上是生活随笔為你收集整理的P5022-旅行【基环树,dfs】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。