Cow Marathon

poj1985:http://poj.org/problem?id=1985

题意:就是树的直径。

题解:直接DFS即可。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+;
struct Node{
int v;
int w;
};
vector<Node>Q[N];
int n,m,k,u,v;
int maxn,start;
void DFS(int u,int f,int len){
if(len>maxn){
maxn=len;
start=u;
}
for(int i=;i<Q[u].size();i++){
if(f!=Q[u][i].v){
DFS(Q[u][i].v,u,len+Q[u][i].w);
}
}
}
int main(){
while(~scanf("%d%d",&n,&m)){
for(int i=;i<=n;i++)
Q[i].clear();
for(int i=;i<=m;i++){
scanf("%d %d %d",&u,&v,&k);
getchar();getchar();
Node temp;temp.v=v;temp.w=k;
Q[u].push_back(temp);
temp.v=u;temp.w=k;
Q[v].push_back(temp);
}
start=,maxn=;
DFS(,,);
maxn=;
DFS(start,,);
printf("%d\n",maxn); }
}
上一篇:Java对象的序列化和反序列化


下一篇:Git (1)