题解

64 条题解

  • 1
    @ 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
    @ 2018-08-05 08:43:04

    两次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
    @ 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;
    }

  • 0
    @ 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
    @ 2014-02-19 23:03:49

    各种逗比程序全部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
    @ 2012-09-22 12:02:18

    100题纪念

  • 0
    @ 2009-11-08 22:39:43

    莫非是巧合?囧囧

    ansistring

  • 0
    @ 2009-10-30 17:33:58

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 290ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:290ms

    囧了

    还有个点要290ms

    两次DFS

    为啥第一次把Easy给卡了......

    就是找树的最长路的方法 因为每两个点之间只有一条路相连

  • 0
    @ 2009-10-26 21:27:39

    假设任意的两个风景点都有且仅有一条路径(无回路)相连。

    深刻地理解这句话。很关键。

  • 0
    @ 2009-10-26 20:59:19

    我瓜了。。。

    牛们看下这个代码。。

    过不了我不明真相。。。。T_T

    #include

    #define MAXN 1000

    #define MAXM 4

    using 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
    @ 2009-10-24 16:22:32

    Accepted 有效得分:100 有效耗时:0ms

    哎,千万要注意r和c的区分....

    因为找一条最长直线,所以还是dfs的好....

  • 0
    @ 2009-10-24 08:41:47

    水货..一次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
    @ 2009-08-27 11:30:00

    二次dfs。。。

    程序:

    http://lifeich1.spaces.live.com/blog/cns!9AB465A9D807BE22!181.entry

    好歹一次AC了。。。

  • 0
    @ 2009-08-10 15:18:28

    一个DFS就是会超时。。。。。

  • 0
    @ 2009-05-27 16:10:16

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    深搜求树中最长链

    先从任意一个可以的点深搜求出到其他点的距离,找到到该点最远的点,再从这个点求一遍到其他点的距离,距离的最大值就是答案。

    复杂度O(n)

  • 0
    @ 2009-05-17 18:09:03

    求树直径,O(N^2)

  • 0
    @ 2009-04-19 15:37:27

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    二次dfs,

    给你数据你就知道为什么了:

    5 5

    .....

    .####

    .....

    ####.

    .....

    输出 16

  • 0
    @ 2009-03-28 12:54:35

    第100题的献礼!

  • 0
    @ 2009-03-25 18:59:20

    我因为[某些]原因,又写长了.

    这个bfs可以放在一个过程里:

    int bfs(int sx,sy){......}

    这个和NOIP 07 TG Core有关.

    这是求无根树直径的很好方法.

  • 0
    @ 2009-02-21 13:45:43

    var

    a:array[0..1010,0..1010] of char;

    i,j,m,n,open,clsed:longint;

    v:array[1..10000,1..2] of integer;

    ans,max:integer;

    procedure search(i,j:integer);

    begin

    if a='.' then

    inc(max);

    a:='#';

    while openans then ans:=max;

       end;

    end;

    writeln(ans-1);

    end.

信息

ID
1107
难度
6
分类
搜索 | 搜索与剪枝 点击显示
标签
(无)
递交数
1214
已通过
342
通过率
28%
被复制
1
上传者