CSU oj 1681 Adjoin（dfs求树上最长路径）（搜索）

拼搏现实的明天。 2022-08-21 12:44 146阅读 0赞

题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1681

题目大意：给你一共有n个结点但是不连通的无向图，你需要用最少的线将其变成连通图，并使连通图中两个的点最长距离最小（一个点可以连接多条线）。

解题思路：最后肯定是将每个图的最长线段的中点连接起来。所以我们要找最长距离，就是找到两个线段最长的图，输出它们线段长度除2相加再加1的结果，特别注意如果拥有最长线段长度的图有三个，那么最后不是加1，而是加二。  
求一个图中最长线段长度两遍dfs即可，第一遍找到最长线段的一个端点，第二遍根据找到的端点再dfs一次即可得到最长的线段长度。

#include <vector>
    #include <list>
    #include <map>
    #include <set>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <bitset>
    #include <algorithm>
    #include <functional>
    #include <numeric>
    #include <utility>
    #include <sstream>
    #include <iostream>
    #include <iomanip>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    #include <ctime>
    #include <cassert>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define Cl0(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    typedef long long LL;
    vector <int> g [100005];
    
    bool used[100005];
    bool used1[100005];
    int ans[100005];
    int maxx,maxxx;
    
    int dfs(int p,int ans)
    {
        used[p]=1;
        used1[p]=1;
        int length=g[p].size();
        int i=0;
        for(; i<length; i++)
        {
            if(!used1[g[p][i]])
            {
                dfs(g[p][i],ans+1);
            }
        }
        if(ans>maxx)
        {
            maxx=ans;
            maxxx=p;
        }
        return maxxx;
    }
    
    int dfs1(int p,int ans)
    {
    
        used1[p]=1;
        int length=g[p].size();
        int i=0;
        for(; i<length; i++)
        {
            if(!used1[g[p][i]])
            {
                dfs1(g[p][i],ans+1);
            }
        }
    
        if(ans>maxx)  maxx=ans;
    
        return maxx;
    }
    
    int main()
    {
        int c,l,num=0;
        while(RII(c,l)!=EOF)
        {
            memset(used,0,sizeof(used));
            for(int i=0; i<l; i++)
            {
                int x,y;
                RII(x,y);
                g[x].push_back(y);
                g[y].push_back(x);
            }
    
            for(int i=0; i<c; i++)
            {
                if(!used[i])
                {
                    memset(used1,0,sizeof(used1));
                    maxx=-1;
                    int v=dfs(i,0);
                    memset(used1,0,sizeof(used1));
                    maxx=-1;
                    ans[num++]=dfs1(v,0);
                }
            }
            sort(ans,ans+num);
            int ans1=ans[num-1];
            int ans2=0,ans3=0;
            if(num>=3)
            {
                if(ans[num-1]==ans[num-2]&&ans[num-2]==ans[num-3])
    
                    ans2=(ans[num-1]+1)/2*2+2;
                else ans2=(ans[num-1]+1)/2+(ans[num-2]+1)/2+1;
            }
            if(num==2) ans2=(ans[num-1]+1)/2+(ans[num-2]+1)/2+1;
            cout<<max(ans1,ans2)<<endl;
            for(int i=0;i<c;i++)
    
            g[i].clear();
        }
        return  0;
    }