1317: Find the max Link
Time Limit: 1 Sec Memory Limit:
128 MB
Description
由N个点组成的无向图，每条边有对应的权值，保证每两点之间存在且仅存在一条路径，一条路径的权值为其所有边的权值之和，请找出一条路径，对于图中每个点至多经过一次,并且这条路径上至少有一条边,这条路径的权值最大。
Input
多组数据(至多30组),第一行两个正整数N,M(2<=N<=50000,1<=M<=50000)，接下来M行，每行三个整数U,V,W(1<=U,V<=N,-100000<=W<=100000)代表在点V,W间有一条权值为W的边。
Output
每组数据输出一行，为一个整数即满足题目要求的路径权值。
Sample Input
4 33 1 -14 2 42 1 5
Sample Output
9
树形DP
d[i][0]表示在i为根的子树中，以i为起点的拥有最大权的路径权值
d[i][0]表示在i为根的子树中，以i为起点的拥有第二大权的路径权值
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define maxn 50011
#define INF -10000000
struct Node {
long long son;
long long w;
};
long long ans;
vector<Node> num[maxn];
long long d[maxn][2];
void DFS(long long x,long long p)
{
long long i,v;
d[x][0]=d[x][1]=INF;
for(i=0;i<num[x].size();i++)
{
v=num[x][i].son;
if(v!=p)
{
DFS(v,x);
if(d[v][0]>0)
{
if(d[x][0]<num[x][i].w+d[v][0])
{
d[x][1]=d[x][0];
d[x][0]=num[x][i].w+d[v][0];
}
else if(d[x][1]<num[x][i].w+d[v][0])
d[x][1]=num[x][i].w+d[v][0];
}
else
{
if(d[x][0]<num[x][i].w)
{
d[x][1]=d[x][0];
d[x][0]=num[x][i].w;
}
else if(d[x][1]<num[x][i].w)
d[x][1]=num[x][i].w;
}
}
}
ans=max(ans,d[x][0]);
ans=max(ans,d[x][0]+d[x][1]);
}
int main()
{
long long N,M;
long long i,u,v;
long long w;
Node tmp;
while(scanf("%lld%lld",&N,&M)==2)
{
for(i=1;i<=N;i++)
num[i].clear();
ans=-10000000;
for(i=1;i<=M;i++)
{
scanf("%lld%lld%lld",&u,&v,&w);
tmp.w=w;
tmp.son=v; num[u].push_back(tmp);
tmp.son=u; num[v].push_back(tmp);
ans=max(ans,w);
}
DFS(1,-1);
printf("%lld\n",ans);
}
return 0;
}