牛客周赛44 F小红的基环树删边

本文主要是介绍牛客周赛44 F小红的基环树删边，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：F-小红的基环树删边

题目大意：给一个基环树，一个n个点，n条边。若是删除第i边，从1到n的最短距离是多少？

思路：因为是基环树，那么从1到n最多就只有二条路径，那么就可以求出不在当前路线上的边删除后的最短路。

//冷静，冷静，冷静
//调不出来就重构 
#pragma GCC optimize(2)
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
//#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld; 
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=998244353;
ll h[N],e[N],ne[N],idx,f[N],w[N];
inline void add(ll a,ll b,ll id)
{w[idx]=id,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
pii p[N];
ll n;
bool st[N];
void dfs(ll x,ll dep)
{if(x==n)//如果搜索到了一条路径，那么用了的边，就被标记出来了 {for(int i=1;i<=n;i++){if(!st[i])//没有标记的边，就算删除了可不会对搜索的路径产生影响 {f[i]=min(f[i],dep);}}}for(int i=h[x];~i;i=ne[i]){ll j=e[i],id=w[i];if(!st[id])//如果当前边没有用过，那么就是可以使用 {st[id]=1;dfs(j,dep+1);st[id]=0;}}
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;memset(h,-1,sizeof(h));for(int i=1;i<=n;i++){ll a,b;cin>>a>>b;f[i]=1e18;add(a,b,i);add(b,a,i);p[i]={a,b};}dfs(1,0);for(int i=1;i<=n;i++){if(f[i]==1e18)f[i]=-1;//如果f[i]的值没有被更新，那么它就是二条路径的必经之路，如果删除就无法到达 cout<<f[i]<<endl;}return 0;
}

这篇关于牛客周赛44 F小红的基环树删边的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---