VIJOS1107 求树的最长链

时间：2022-01-23 23:34:40

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过.....代码写得太挫了...

相关文章