首页 > 代码库 > VIJOS1107 求树的最长链
VIJOS1107 求树的最长链
vijos1107环游大同80天
学习了一下求树的最长链的方法
最简单的思路就是两次dfs
两次dfs分别有什么用呢？
第一次dfs，求出某个任意的点能到达的最远的点
第二次dfs，从所搜到的最远的点倒搜回去.
为什么需要两次呢？
其实很容易想通第一遍dfs的起始点或许并不是最长链的起点
从最远的点倒搜到的最长的链就是所求的解
（因为最长链一定经过这个最远的点啊...
这里注意题目表述：
假设任意的两个风景点都有且仅有一条路径（无回路）相连。显然，任意一个风景点都可以作为游览路线的起点或者终点。
这里就保证了题目中只有一个连通块，也就是从可走的任意点开始第一遍dfs都是可行的
mark一个小技巧的东西：
因为之前没有看清题目..就把所有的可以走的点都两遍dfs了..
T是肯定的...但是被D说dfs写得太丑...之前用vis[][] 记录是否搜过该点，需要每次dfs之前都memset一次，很浪费时间
学长表示可以每次dfs的时候+a，然后比较是否和之前递归进来的相等即可
然后附上这题代码：
#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;bool f[1001][1001];int vis[1001][1001];int temp=0,ans=0,maxn=0,maxx=0,markx,marky;int dx,dy;int n,m;char s;bool f1;void dfs(int x,int y,int sum){ if(x<0 || x>n || y<0 || y>m || (vis[x][y]==vis[markx][marky] && !f1)){ if(sum>maxx){ maxx=sum; dx=x; dy=y; } return; } vis[x][y]++; f1=0; if(f[x-1][y]) dfs(x-1,y,sum+1); if(f[x+1][y]) dfs(x+1,y,sum+1); if(f[x][y-1]) dfs(x,y-1,sum+1); if(f[x][y+1]) dfs(x,y+1,sum+1);}int main(){ //freopen("data.txt","r",stdin); scanf("%d%d",&n,&m); memset(f,false,sizeof(f)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ cin>>s; if(s==‘.‘) f[i][j]=1; } memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ ans=0; if(f[i][j]){ f1=1; markx=i;marky=j; dfs(i,j,0); break; } } f1=1; markx=dx;marky=dy; dfs(dx,dy,0); printf("%d",maxx); return 0;}
编译成功
测试数据 #0: Accepted, time = 46 ms, mem = 5384 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 5364 KiB, score = 20
测试数据 #2: Accepted, time = 421 ms, mem = 5364 KiB, score = 20
测试数据 #3: Accepted, time = 187 ms, mem = 5412 KiB, score = 20
测试数据 #4: Accepted, time = 0 ms, mem = 5368 KiB, score = 20
Accepted, time = 654 ms, mem = 5412 KiB, score = 100
没有0ms过.....代码写得太挫了...
VIJOS1107 求树的最长链