64 条题解
-
1
PowderHan LV 10 @ 2017-05-08 07:57:39
/* 树上最长链 和直径差不多叭 我就不多说了找了几个挺好的博客的 { 学习了一下求树的最长链的方法 最简单的思路就是两次dfs 两次dfs分别有什么用呢？ 第一次dfs，求出某个任意的点能到达的最远的点 第二次dfs，从所搜到的最远的点倒搜回去. 为什么需要两次呢？ 其实很容易想通第一遍dfs的起始点或许并不是最长链的起点 从最远的点倒搜到的最长的链就是所求的解 因为最长链一定经过这个最远的点啊... 这里注意题目表述： 假设任意的两个风景点都有且仅有一条路径（无回路）相连。 显然，任意一个风景点都可以作为游览路线的起点或者终点。 这里就保证了题目中只有一个连通块，也就是从可走的任意点开始第一遍dfs都是可行的 } { 本题是一道简单求最长链问题，题解简单得只有一句话——两次搜索即可。但是怎么证明倒是一个需要想想的问题。 假设任意的两个风景点都有且仅有一条路径（无回路）相连。由此，本题求的就是两个叶子之间的最长链。 对于第一次搜，我们任选一个叶子A。然后找到离它最远的那一片叶子B，再做一次，找到max即可。 证明： 找到A，B后，可得A或B必为最长链的端点。易知不存在最长链CD与AB相交的情况（那样A不会搜索到B）。 假设存在最长链CD与A，B不接触则EB>EF+FD,FD>EF+EB.根据不等式的同向相加性质，EB+FD>EF+EF+EB+FD.所以2EF<0。 显然不符合题意。所以最长链必与A点，或B点相交。 综上所证，此题只需要做两次搜索就解决了。本人真心偷懒，做了个DFS，显然BFS更优。 } { 我采用的是两次 DFS 的方法，也就是任意取一个点开始 DFS，找到这次 DFS 时深度最深的点（也就是从所选点开始最长路径的终点）， 然后从这一点（可以证明，这一点是最长路径的端点）开始再进行 DFS，这次 DFS 的深度就是要求的路径长度。 算法就是这样了，不过这个算法的正确性我一开始也不太确定，下面来证明一下： 设最长路径为 AB ，一开始任选的点为 P。取路径 PB 上的一点 Q，使得 AQ 与 PQ 只有一个公共点 Q（ 也就是使得从 A 走到 Q 再走到 B 不会走回头路）。设 AQ=a，QB=b，QP=s，不妨设 a<b。 要证明这个算法的正确性，也就是要证明从 P 开始的最长路径的终点一定是 A 或 B。 假设从 P 开始的最长路径的终点是 C ，设 CP=c。 由假设知， c>s+b。由于从从 P 开始的最长路径的终点是 C，所以第二次 DFS 将从 C 开始， 所得最长路径为 CB=c+s+b>s+b+s+b，又因为 a<b，故CB>s+b+s+b>s+a+s+b>a+b=AB，这与 AB 是最长路径矛盾， 故假设不成立，命题得证。 时间复杂度 O(CR)，空间复杂度 O(CR)。 } 然后就这样了 我也比较懒 写个dfs滚粗了 一开始直接写了个所有点深搜结果发现sb了 OTZ */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int MAXN=1005; int a[MAXN][MAXN]; bool v[MAXN][MAXN]; int zx[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; int n,m; int ans; int maxx,maxy; void init() { cin>>m>>n; char ch; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>ch; if(ch=='.') a[i][j]=1; } } void dfs(int x,int y,int w) { if(w>ans) { ans=w; maxx=x; maxy=y; } for(int i=0;i<4;i++) { int newx=x+zx[i][0]; int newy=y+zx[i][1]; if(a[newx][newy]&&!v[newx][newy]) { v[newx][newy]=1; dfs(newx,newy,w+1); v[newx][newy]=0; } } } int main() { init(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]) { v[i][j]=1; dfs(i,j,0); v[i][j]=0; break; } v[maxx][maxy]=1; dfs(maxx,maxy,0); cout<<ans<<endl; return 0; } -
0
两次dfs求树上最长路径
#include <bits/stdc++.h> using namespace std; #define FOR(i,n) for (int i=1;i<=n;i++) #define REP(i,a,b) for (int i=a;i<=b;i++) #define pb push_back #define mp make_pair #define ll long long const int N=100000+10; const int inf=0x3f3f3f3f; const ll mod=7654321; const double PI=3.1415926; const double eps=1e-8; int m,n; bool a[1001][1001]; int dx[]={0,1,0,-1,0}; int dy[]={0,0,1,0,-1}; vector<int> g[1000001]; int root,root_dep; int ans; bool ok(int x,int y) { return 1<=x&&x<=n&&1<=y&&y<=m; } void insert(int x,int y) { g[x].pb(y); } int encode(int x,int y) { return (x-1)*m+y; } void dfs(int x,int fa=0,int dep=0) { ans=max(ans,dep); if (!root) root=x,root_dep=dep; else { if (root_dep<dep) { root_dep=dep; root=x; } } for (int i=0;i<g[x].size();i++) { int y=g[x][i]; if (y!=fa) { dfs(y,x,dep+1); } } } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); cin>>m>>n; FOR(i,n) FOR(j,m) { char t='\n'; while (t=='\n') cin>>t; if (t=='.') a[i][j]=1; } FOR(i,n) FOR(j,m) if (a[i][j]) { int x,y; FOR(k,4) { x=i+dx[k],y=j+dy[k]; if (ok(x,y)&&a[x][y]) { insert(encode(i,j),encode(x,y)); } } } FOR(i,n) { bool flag=0; FOR(j,m) if (a[i][j]) { dfs(encode(i,j)); flag=1; break; } if (flag) break; } dfs(root); cout<<ans<<endl; return 0; } -
0
1263659722 LV 10 @ 2016-11-04 10:07:43
**出题人！！为什么起点不算。。。WA好久。。。
#include<bits/stdc++.h>
#define pi acos(-1.0)
#define ll long long
#define N 1005
#define INF 0x7fffffff
using namespace std;
int n,m;
char s[N];
int a[N][N];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int flag[N][N];
int maxx,maxy;
int ans=0;
void dfs(int x,int y,int step)
{
a[x][y]=0;
if(step>ans)
{
ans=step;
maxx=x;
maxy=y;
}
for(int i=0;i<4;i++)
{
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<=n&&yy<=m&&xx>=1&&yy>=1&&a[xx][yy]==1)
dfs(xx,yy,step+1);
}
a[x][y]=1;
}
int main()
{
//freopen("D://in.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);
for(int j=1;j<=m;j++)
a[i][j]=(s[j]=='.'?1:0);
}
int tmp=0;
for(int i=1;i<=n;i++)
{
if(tmp)
break;
for(int j=1;j<=m;j++)
{
if(a[i][j]==1)
{
dfs(i,j,0);
tmp=1;
break;
}
}
}
memset(flag,0,sizeof(flag));
dfs(maxx,maxy,0);
printf("%d",ans);
return 0;
}-
200题纪念。。。
-
-
0
xiangshang12 LV 8 @ 2014-10-26 21:33:27
楼下的你被Markdown坑了。。。。我来帮你
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<fstream>
using namespace std;
bool f[1001][1001];
int maxx, maxy;
int n, m, ans = 0;
void DFS(int d, int x, int y)
{
f[x][y] = 1;if(d > ans)
{
maxx = x;
maxy = y;
ans = d;
}if(x + 1 <= n && f[x + 1][y] == 0) DFS(d + 1, x + 1, y);
if(x - 1 > 0 && f[x - 1][y] == 0) DFS(d + 1, x - 1, y);
if(y + 1 <= m && f[x][y + 1] == 0) DFS(d + 1, x, y + 1);
if(y - 1 > 0 && f[x][y - 1] == 0) DFS(d + 1, x, y - 1);
f[x][y] = 0;
}
int main()
{
char k;
int x, y;
scanf("%d%d\n", &n, &m);for(int i = 1; i <= n; i++) for(int j = 1; j <= m + 1; j++)
{
scanf("%c", &k);if(k == '#') f[i][j] = 1;
else if(k == '.')
{
maxx = x = i;
maxy = y = j;
f[i][j] = 0;
}
}DFS(0, x, y);
DFS(0, maxx, maxy);
printf("%d\n", ans);
return 0;
} -
0
各种逗比程序全部CE，无语，还是我来发善心贴正解吧，别被坑了AC率
#include<stdio.h>
#include<string.h>
bool f[1001][1001];
int maxx,maxy;
int n,m,ans=0;
void DFS(int d,int x,int y)
{
f[x][y]=1;
if(d>ans)
{
maxx=x;
maxy=y;
ans=d;
}
if(x+1<=n && f[x+1][y]==0) DFS(d+1,x+1,y);
if(x-1>0 && f[x-1][y]==0) DFS(d+1,x-1,y);
if(y+1<=m && f[x][y+1]==0) DFS(d+1,x,y+1);
if(y-1>0 && f[x][y-1]==0) DFS(d+1,x,y-1);
f[x][y]=0;
}
int main()
{
char k;
int x,y;
scanf("%d%d\n",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m+1;j++)
{
scanf("%c",&k);
if(k=='#')
f[i][j]=1;
else if(k=='.')
{
maxx=x=i;maxy=y=j;
f[i][j]=0;
}
}
DFS(0,x,y);
DFS(0,maxx,maxy);
printf("%d\n",ans);
return 0;
} -
0
我瓜了。。。
牛们看下这个代码。。
过不了我不明真相。。。。T_T
#include
#define MAXN 1000
#define MAXM 4using namespace std;
int n,m;
char a[MAXN+1][MAXM+1];
bool hash[MAXN+1][MAXM+1];
int sx,sy,Ans = 0;
const int fx[] = {0,1,0,-1};
const int fy[] = {1,0,-1,0};
void dfs(int x,int y,int step){
hash[x][y] = true;
if (step>Ans){
Ans = step;
sx = x,sy = y;
}
for (int i = 0; i=1&&tx=1&&ty -
0
水货..一次AC..
var map:array[0..1023,0..1023]of char; vis:array[0..1023,0..1023]of boolean; m,n,maxdep,i,j,sx,sy,dx,dy:integer;procedure dfs(dep,x,y:integer);begin if (xn) or (ym) then exit; if vis[x,y] then exit; if dep>maxdep then begin maxdep:=dep; dx:=x; dy:=y; end; vis[x,y]:=true; if map[x-1,y]'#' then dfs(dep+1,x-1,y); if map[x+1,y]'#' then dfs(dep+1,x+1,y); if map[x,y-1]'#' then dfs(dep+1,x,y-1); if map[x,y+1]'#' then dfs(dep+1,x,y+1);end;begin readln(m,n); for i:=1 to m do begin for j:=1 to n do begin read(map); if map='.' then begin sx:=i; sy:=j; end; end; readln; end; fillchar(vis,sizeof(vis),0); maxdep:=-1; dfs(0,sx,sy); fillchar(vis,sizeof(vis),0); maxdep:=-1; dfs(0,dx,dy); writeln(maxdep);end.
-
0
二次dfs。。。
程序：http://lifeich1.spaces.live.com/blog/cns!9AB465A9D807BE22!181.entry
好歹一次AC了。。。 -
0
zhengfangyi LV 10 @ 2009-03-28 12:54:35
第100题的献礼!
-
0
gnaggnoyil LV 10 @ 2009-03-25 18:59:20
我因为[某些]原因,又写长了.
这个bfs可以放在一个过程里:
int bfs(int sx,sy){......}
这个和NOIP 07 TG Core有关.
这是求无根树直径的很好方法.
PowderHan
LV 10
@ 2017-05-08 07:57:39
