首页 > 代码库 > 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 奶牛马拉松