牛客练习赛40 C-小A与欧拉路

佚名 6年前 (2019-04-15) 随笔 2040人围观抢沙发百度已收录

求图中最短的欧拉路。
题解：因为是一棵树，因此当从某一个节点遍历其子树的时候，如果还没有遍历完整个树，一定还需要再回到这个节点再去遍历其它子树，因此除了从起点到终点之间的路，其它路都被走了两次，而我们要求总的路程最短，那么我们就让从起点到终点的路最长即可，也就是树的直径。所以答案就是所有边权的两倍再减去树的直径

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector>
using namespace std; typedef long long LL; const int maxn=200005; int n; struct Edge { int from,to; LL val; }; vector<Edge>edge[maxn]; LL dp[maxn][2]; void dfs(int u,int fa) { dp[u][0]=0;dp[u][1]=0; int len=edge[u].size(); for(int i=0;i<len;i++) { int v=edge[u][i].to; LL w=edge[u][i].val; if(v==fa) continue; dfs(v,u); if(dp[v][0]+w>dp[u][0])//如果以u为根节点的最长链可以被它的儿子v更新
 { dp[u][1]=dp[u][0];//最长链变次长链
            dp[u][0]=dp[v][0]+w;//最长链被更新
 } else if (dp[v][0]+w>dp[u][1])//如果不能更新最长链但是却可以更新次长链
            dp[u][1]=dp[v][0]+w; } } int main() { scanf("%d",&n); LL ans=0; int f,t;LL v; Edge temp; for(int i=1;i<n;i++) { scanf("%d %d %lld",&f,&t,&temp.val); temp.from=f;temp.to=t; edge[f].push_back(temp); temp.from=t;temp.to=f; edge[t].push_back(temp); ans+=(temp.val*2); } dfs(1,0); LL maxx=0; for(int i=1;i<=n;i++) maxx=max(maxx,dp[i][0]+dp[i][1]); printf("%lld\n",ans-maxx); return 0; }

网看到了一个bfs 求树的直径的解法：贴一下

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include <iostream> #include <cstring> #include <queue>
using namespace std; typedef long long ll; const int MAX = 1e6+100; struct hh{ int u,v,w; int nt; }a[MAX]; int dis[MAX],head[MAX]; bool vis[MAX]; int n,tot,point,len; ll ans;//注意要用long long
void add(int u,int v,int w){ a[tot].v=v; a[tot].u=u; a[tot].w=w; a[tot].nt=head[u]; head[u]=tot++; } void bfs(int s){//找树的直径模板
    memset(vis,false,sizeof(vis));//第二次要初始化，第一次一块带上了，嘻嘻~~不超时
    memset(dis,0,sizeof(dis));//第二次要初始化，第一次一块带上了，嘻嘻~~不超时
    queue<int> q; q.push(s); vis[s]=1; while(!q.empty()){ int x=q.front(); q.pop(); for (int i = head[x]; ~i; i = a[i].nt){ int y=a[i].v; if(!vis[y]){ dis[y]=dis[x]+a[i].w; if(len<dis[y]){ len=dis[y]; point=y; } vis[y]=true; q.push(y); } } } } int main(){ cin >> n; memset(head,-1,sizeof(head)); for (int i = 0; i < n-1;i++){ int u,v,w; cin >> u >> v >> w; add(u,v,w);//无向边，为双向的
 add(v,u,w); ans+=w<<1;//树的权值*2
 } len=0; bfs(1);//找到最远点
    len=0;//len为树的直径~~，记住要初始化！
    bfs(point);//找直径，必须跑两边，记住！！！
    cout << ans-len << endl; return 0; }