View Code /* 【题目来源】http://soj.me/show_problem.php?pid=1003&cid=567【题目分析】给定一些边确定一个图，即给定一些点之间的连通情况，保证给定的图没有回路，要求输出该图存在的最长路径。 【思路分析】. 根据给定信息构造图，用邻接表表示。（邻接矩阵明显很麻烦且效率不高） . 将每一个顶点看成是树根，求出树的高度。. 得到一系列树的高度，最大的那个就是图中存在的最长路径。嗯对的。 【陷阱分析】.不应该被数据蒙骗，比如只给两条边但顶点不一定是1,2,3而有可能是1,99,100之类，所以数组开最大（题目范围1-100，所以开个105绝对够了） 【小小感受】用vector构造邻接表确实比较方便~ 学习了 */#include#include #include #include #include using namespace std;#define Max 105int main(){ int m; cin >> m; while (m--) { int n; cin >> n; vector v[Max];//用vector构造邻接表 bool visit[Max];//记录该点是否已经被访问过 //构造邻接表 int temp1, temp2; for (int i = 0; i < n; ++i) { cin >> temp1 >> temp2; v[temp1].push_back(temp2);//无向图 temp1通temp2 v[temp2].push_back(temp1);//无向图 temp2通temp1 } int ans = 0; //广搜咯~~~~ 求树的高度 for (int i = 1, j = 1; j < 3; j++) { int height[Max] = { 0}; memset(visit, 0, sizeof(visit)); queue q; q.push(i); visit[i] = 1; while (!q.empty()) { int current = q.front(); q.pop(); for (int j = 0; j < v[current].size(); ++j) if (!visit[v[current][j]]) { q.push(v[current][j]); height[v[current][j]] = height[current]+1;//current所连接的节点的高度要比current多1 （其实这里理解成深度会更好） visit[v[current][j]] = 1; } i = current; } int max = *max_element(height, height+Max);//该点作为树根时树的高度 if (ans < max) ans = max;//更新最大值 } cout << ans << endl; }}
View Code /*受乔帮主提点，这道题果然有更简单的做法 【思路分析】通俗来讲，把给定的图看成是一串珠子，随便拿起其中一颗，吊起来，那么再拿起此时这串珠子最下面的那颗，再吊起来ok，那么这时这串珠子的高度就是这一整个图存在的最长路径。好神奇。我自己粗略的证明 ：随便拿起的这颗记为A，最底下那颗记为B。拿起A:此时B一定是最长路径里面的一点。 注意，此时A到B之间必定至少有2点是属于最长路径的，即除了B外还至少有一点C，并且这一点C在 A 到 A和B的中间。（若有多点，则C取最高的那一点） （为什么C不能在B 到 A和B的中间呢，反证一下即可）离C最远的点现在必定是B 拿起B：现在离C最远的必定是最低的那点D，所以综合C在最长路径上，C离B最远，可得出BD为最长路径。 【小小疑问】 既然开始时是随机选一点，我还是不知道为什么选1就对，选temp2就不对。 */#include#include #include #include #include using namespace std;#define Max 105int main(){ int m; cin >> m; while (m--) { int n; cin >> n; vector v[Max];//用vector构造邻接表 bool visit[Max];//记录该点是否已经被访问过 //构造邻接表 int temp1, temp2; for (int i = 0; i < n; ++i) { cin >> temp1 >> temp2; v[temp1].push_back(temp2);//无向图 temp1通temp2 v[temp2].push_back(temp1);//无向图 temp2通temp1 } int ans = 0; //循环2次就行啦~~~ for (int i = 1, j = 1; j < 3; j++) { int height[Max] = { 0}; memset(visit, 0, sizeof(visit)); queue q; q.push(i); visit[i] = 1; while (!q.empty()) { int current = q.front(); q.pop(); for (int j = 0; j < v[current].size(); ++j) if (!visit[v[current][j]]) { q.push(v[current][j]); height[v[current][j]] = height[current]+1;//current所连接的节点的高度要比current多1 （其实这里理解成深度会更好） visit[v[current][j]] = 1; } i = current; } int max = *max_element(height, height+Max);//该点作为树根时树的高度 if (ans < max) ans = max;//更新最大值 } cout << ans << endl; }}