首页 > 代码库 > BZOJ 3363: [Usaco2004 Feb]Cow Marathon 奶牛马拉松
BZOJ 3363: [Usaco2004 Feb]Cow Marathon 奶牛马拉松
Description
给你一个图,两个点至多有一条路径,求最长的一条路径. \(n \leqslant 4\times 10^4\)
Sol
DFS?DP?
这就是一棵树,方向什么的都没用...
然后记录一下到这个点的最大值和次大值更新答案即可.
Code
/************************************************************** Problem: 3363 User: BeiYu Language: C++ Result: Accepted Time:116 ms Memory:5572 kb****************************************************************/ #include<cstdio>#include<vector>#include<utility>#include<iostream>using namespace std; #define mpr make_pairtypedef pair< int,int > pr;const int N = 40005; int n,m,ans;vector<pr> g[N];int mx1[N],mx2[N],b[N]; inline int in(int x=0,char ch=getchar()){ while(ch>‘9‘ || ch<‘0‘) ch=getchar(); while(ch>=‘0‘ && ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();return x; }void DFS(int u,int fa){ b[u]=1; for(int i=0,v,d;i<g[u].size();i++) if((v=g[u][i].first)!=fa){ DFS(v,u),d=g[u][i].second; if(mx1[v]+d>mx1[u]) mx2[u]=mx1[u],mx1[u]=mx1[v]+d; else if(mx1[v]+d>mx2[u]) mx2[u]=mx1[v]+d; }ans=max(ans,mx1[u]+mx2[u]);}int main(){ n=in(),m=in(); for(int i=1,u,v,w;i<=m;i++){ u=in(),v=in(),w=in(); g[u].push_back(mpr(v,w)),g[v].push_back(mpr(u,w)); } for(int i=1;i<=n;i++) if(!b[i]) DFS(i,-1); cout<<ans<<endl; return 0;}
BZOJ 3363: [Usaco2004 Feb]Cow Marathon 奶牛马拉松
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。