发现n年前草稿。。
最直接思路就是深搜，用 T *g[] 这种形式来构造邻接链表，注意是无向图。
从出发点开始搜，标记已访问点，遍历未访问的邻接点，把所有可能都计算一次，
全局变量记录最大距离。
很不幸，不知为何超时。（后来发现时忘记 把图清空了）
后来想了想，似乎没说图中有无环，有无孤立点。
应该做访问标记的是 边，而不是点。于是开始胡思乱想怎么才能快速判断 边 是否已访问。
根据 两端点号 a*b*17%n 进行 hash 似乎可以。
接着又想 深搜会不会太多 分支会超时？
n点仅有n-1边，十分稀疏啊，应该没问题。
网上搜到几个题解，试试自己设计的数据，发现总是 比自己预期结果少算一条边。
因为我的数据设计是有环 和 孤立点的， 从结果来看来应该 题目需要的图是无环的。
再后来，看了几遍题目，发现一句超级重要的：
There are N cities and N-1 roads in Magic-Island. You can go from one city to any other.
后面那句就是说图是连通的，没有孤立点！
再加上 n点n-1边， 图就是无环的。
咳咳，所以这图就是一颗树。
所以 访问标记 可以对边 也可以对点 做；
图的存储还是 之前的邻接表；
要深 要广 随你搜。
我的代码自己实现了简单的 vector<T> g[n]， 性能应该没有stl 的那么好。
| 0.12sec | 1344 KB |
#include <cstdio>
#include <cstring>
int maxDis;
char isVisited[10001];
struct node{int dis, dst;void show() const{printf("[%d %d], ", dst, dis );};
};template< typename T >
struct adjlst{enum { initCapacity=2, extendTimes=2, }; /* initCapacity 初始邻接点容量， extendTimes扩容倍数。 */T **a;int num, *count, *max; /* num 总共点数， count邻接点数目， max 最大容量。*/adjlst( int n ){ num = n;a = new T*[n]; count = new int[n];max = new int[n];for( int i=0; i<n; i++){ //初始化邻接表只有 initCapacity 容量。 a[i] = new T[initCapacity];max[i] = initCapacity;count[i] = 0;}}~adjlst(){for( int i=0; i<num; i++ )delete [] a[i];delete [] a ;delete [] count ;delete [] max ;}void addNode( int row, const T& x ){int i, pos;if( count[row] >= max[row] ){ // 满了，需要扩容 extendTimes 倍 max[row] *= extendTimes;T* temp = new T[ max[row] ];//for( i=0; i<count[row]; i++ ) temp[i] = a[row][i];memcpy( temp, a[row], sizeof(T)* count[row] );delete [] a[row];a[row] = temp;}pos = count[row]++; a[row][pos] = x;/*x.show();printf("\n");*/}void show( int st, int ed ) const{int i,j, n;for( i=st; i<ed; i++ ){printf("--- %d %d: ", max[i], i );n = count[i];for( j=0; j<n; j++ )a[i][j].show();printf("\n");}} void clear(){memset( count, 0, sizeof(count[0])*num );}
};void dfs( const adjlst<node>&g, int st, int curDis ){int i,j,n, dis, dst;n = g.count[st];if( curDis > maxDis ) maxDis = curDis; for( i=0; i<n; i++ ){dst = g.a[st][i].dst;if( isVisited[ dst ] == 0 ){isVisited[ dst ] = 1;dis = g.a[st][i].dis;dfs( g, dst, curDis+dis );// printf("====%d\n", maxDis );isVisited[ dst ] = 0;}}
}int main(){int num_city, capital, i, src,dst;node temp;adjlst<node> graph( 10001 );while(scanf( "%d %d", &num_city, &capital ) != EOF ){for( i=1; i<num_city; i++ ){ // 插入 n-1 条边 scanf("%d %d %d", &src, &dst, &temp.dis );temp.dst = dst;graph.addNode( src, temp );temp.dst = src;graph.addNode( dst, temp );}//graph.show(0, num_city );maxDis = 0;memset( isVisited, 0, sizeof(isVisited) );isVisited[ capital ] = 1;dfs( graph, capital, 0 );printf ( "%d\n", maxDis );graph.clear();}return 0;
}
AC之后又有新的问题了。
如何生成随机数据？
要保证数据生成的图是无环，连通的该怎么搞？