Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 供WA参考

Posted by creativewang at 2012-10-10 22:37:14 on Problem 2631
```写得还算可以，不过花的时间有点长……
/*
* POJ-2631
* mike-w
* 2012-10-10
* ******************************
* find the diameter of a tree
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAXSIZE 11111
#define QSIZE 22222
#define INF 9999999
#define DISP_GRAPH
#define FOO_DEBUG

int maxn;
int tag[MAXSIZE];

int comp(const void *e1, const void *e2)
{
return *((int*)e1) - *((int*)e2);
}

int build_graph(void)
{
int i;
qsort(edge, lsize, sizeof(int[3]), comp);
for(i=1; i<lsize; i++)
if(edge[i][0]!=edge[i-1][0])
return 0;
}

int enque(int x)
{
que[qtail++]=x;
qtail%=QSIZE;
qlen++;
return 0;
}

int deque(void)
{
qlen--;
return ret;
}

int bfs(int src)
{
int i, x;
memset(tag, 0, sizeof(tag));
tag[src]=1;
enque(src);
while(qlen>0)
{
x=deque();
if(!tag[edge[i][1]])
{
tag[edge[i][1]]=edge[i][2]+tag[x];
enque(edge[i][1]);
}
}
return 0;
}

int max(int e1, int e2)
{
return e1>e2?e1:e2;
}

#ifdef DISP_GRAPH
int disp_graph(void)
{
int i, j;
puts("*GRAPH+++++++++++++++++++++++++++");
for(i=0; i<=maxn; i++)
{
printf("* %2d +\n", i);
printf("     |- %2d (len=%2d)\n", edge[j][1], edge[j][2]);
}
putchar('\n');
return 0;
}
#endif

int main(void)
{
int t1, t2, t3, i, maxl, maxi;

while(scanf("%d%d%d", &t1, &t2, &t3)!=EOF)
{
edge[lsize][0]=t1;
edge[lsize][1]=t2;
edge[lsize][2]=t3;
lsize++;
edge[lsize][0]=t2;
edge[lsize][1]=t1;
edge[lsize][2]=t3;
lsize++;
maxn=max(max(t1, t2), maxn);
}
build_graph();
#ifdef DISP_GRAPH
disp_graph();
#endif

bfs(edge[0][0]);
maxl=0, maxi=0;
for(i=0; i<=maxn; i++)
if(tag[i]>maxl)
maxl=tag[i], maxi=i;
#ifdef FOO_DEBUG
printf("one point of the diameter = %d\n", maxi);
#endif

bfs(maxi);
maxl=0;
for(i=0; i<=maxn; i++)
if(tag[i]>maxl)
maxl=tag[i], maxi=i;
#ifdef FOO_DEBUG
printf("the other point of the diameter = %d\n", maxi);
#endif
printf("%d\n", maxl-1);
return 0;
}

```

Followed by: