sicily 1024 magic island

本文主要是介绍sicily 1024 magic island，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

发现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之后又有新的问题了。

如何生成随机数据？

要保证数据生成的图是无环，连通的该怎么搞？

 

 

 

 

 

这篇关于sicily 1024 magic island的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---