旅行(基环树)
m=n-1或m=n,所以要么是树,要么是基环树
如果是一棵树,直接深搜遍历所有方案
如果是基环树,由于此题数据范围不是很大,直接暴力枚举删掉每一条边
(假删,只需要做个标记即可)
删掉后,再深搜
不用把环找出来再删边,因为如果我们删的不是环上的边,那树肯定就有一个地方
断开了,就不可能遍历到所有的点,所以这种情况也不可能是最优解
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=5010;
vector<int> g[N];
bool st[N];
PII edge[N];
int n,m,v1,v2,cnt,better;
vector<int> path(N,N);//数组大小为N,数组中的每个数初始化为N
bool dfs(int u){
if(!better){//better判断当前路径是否比之前优,1:比之前优 0:跟之前一样 不如之前就直接返回了
if(u>path[cnt])return false;//当前路径大于之前路径的最优值,直接剪枝儿
if(u<path[cnt])better=1;
//当前路径比之前优,则一定要走完该路,better一直为1即可
}
st[u]=true;//标记u被搜过了
path[cnt++]=u;//更新路径
for(int i=0;i<g[u].size();i++){//枚举u的所有邻点
int j=g[u][i];
if(st[j])continue;
if((j==v1&&u==v2)||(j==v2&&u==v1))continue;//如果是删掉的边,则不能走
if(!dfs(j))return false;
/*
解释一下这里为什么是return false而不是continue
因为!dfs(j)只有两种情况:
1、j与之前的第cnt个数相同,j后面的某一个数大于
2、j直接就大于之前的第cnt个数
这两种情况都可以断定u的邻点中j后面的数一定不可能是最优的,因为它们都大于j
*/
}
return true;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
edge[i]={a,b};
}
//给每个点的邻点从小到大排序
for(int i=1;i<=n;i++)
sort(g[i].begin(),g[i].end());
if(m==n-1)dfs(1);//m=n-1,树,复杂度O(n)
else{//m=n,基环树
//直接暴力枚举所有边,然后删边,复杂度O(n^2)不会超时
for(int i=1;i<=m;i++){
memset(st,false,sizeof st);
v1=edge[i].first,v2=edge[i].second;
cnt=better=0;
dfs(1);
}
}
for(int i=0;i<n;i++)
cout<<path[i]<<' ';
cout<<endl;
return 0;
}