louisfghbvc的部落格

思路1:

水之呼吸第87式測資騙你，測資90000(? ，900就過，解法floyd warshall演算法，找出所有點到點的最短路徑，在找每個點的偏心率，題目有說明偏心率為該點到其他點的最長距離。而中心點只要等於半徑，半徑為偏心率最小者。不過90000的話這種解法過不瞭(陣列空間不夠)，只能說測資有點水。上代碼吧。時間複雜度O(N^3)。簡單易懂但是慢。

代碼1:

#include <iostream>
#include <cstring>
#include <vector>
#define MN 900
#define MX 99999
using namespace std;
int et[MN], rad; // rad 為半徑 , et紀錄偏心率
int main()
{
    int k, n, a, b;
    cin >> k;
    while(k--){
        cin >> n;
        vector< vector <int> > d(MN, vector<int>(MN, MX)); // 90000無法，global變數也無法，先令所有點距離為無限大
        for(int i = 0; i < n - 1; ++i){
            cin >> a >> b;
            d[a][b] = 1;
            d[b][a] = 1;
        }
        memset(et, 0, sizeof et);
        rad = MX;
        for(int k = 0; k < n; ++k){
            for(int i = 0; i < n; ++i){
                for(int j = 0; j < n; ++j){
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]); // floyd warshall演算法 以k當斷點，看是否這個斷點切開的兩段路，能比原本小
                }
            }
        }

        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j)
                if(i != j)
                    et[i] = max(et[i], d[i][j]);  // 找每個點(n個)的離心率，為i到其他點(j)最大
        }

        for(int i = 0; i < n; ++i){
            rad = min(et[i], rad);  // 離心率之最小為半徑且為中心點
        }

        for(int i = 0; i < n; ++i){ // 從0開始找，等於半徑就是中心並且跳出迴圈。
            if(et[i] == rad){ 
                cout << i << "\n";
                break;
            }
        }

    }
    return 0;
}

思路2:

進階的方法O(N)，也可以過。首先dfn[i]為直徑起點到i的距離，答案就結束了

大方向是: 找樹的直徑->找樹的中心。

我用了2次dfs，第1次為從隨意一點走，找出直徑上的其中一點，第2次從直徑那點走，並更新dfn距離。最後在看從點i到直徑點距離有沒有=半徑，由小至大，找到就停止。中心點最多兩個，假設直徑長度=偶數，就1個。直徑基數的話，半徑可能是中點或中點+1。

那麼重點在於為啥從隨意一點走，最遠的那點必為直徑的一端點呢? (自己畫圖想一想囉!! 從任意一點走一定會走到葉子或根結點)

代碼2:

#include <bits/stdc++.h>
#define N 90005
using namespace std;
vector<int> adj[N];
int dfn[N], mx, id; //dfn為任意一點到直徑點的距離, mx = 直徑, id為直徑點
bool vis[N];
void dfs(int u){
    for(int i = 0; i < adj[u].size(); ++i){
        int v = adj[u][i];
        if(vis[v])
            continue;
        vis[v] = true;
        dfn[v] = dfn[u] + 1;
        if(mx < dfn[v]){
            mx = dfn[v]; //更新最大直徑
            id = v;
        }
        dfs(v);
    }
}
int main()
{
    int k, n;
    cin >> k;
    while(k--){
        cin >> n;
        for(int i = 0; i < n; ++i){
            adj[i].clear();
            vis[i] = false;
        }
        for(int i = 1; i < n; ++i){
            int a, b;
            cin >> a >> b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        mx = 0;
        dfn[0] = 0;
        dfs(0);

        memset(vis, 0, sizeof vis);
        mx = 0;
        dfn[id] = 0;
        dfs(id);

        int mid = mx / 2, mid1 = -1;
        if(mx & 1)
            mid1 = mx / 2 + 1; //基數的話中心點有兩種
        for(int i = 0; i < n; ++i){
            if(dfn[i] == mid || dfn[i] == mid1){
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}
/*測資範例輸入
2
5
0 1
1 2
1 3
3 4
15
1 0
2 1
3 1
4 0
5 4
6 4
7 5
8 6
9 7
10 4
11 7
12 5
13 11
14 11
*/