SRM630 Div1 Easy "Egalitarianism3"

問題

TopCoder Statistics - Problem Statement

考えたこと

頂点が２つ以上あれば、適当な頂点を２つ選ぶことで必ずkを2にすることができる。kを3以上にするには、最短パスで共通的に使う頂点cがなければならない。頂点u, v, wからcへの最短パスの距離が同じであり、かつcを取り除いたグラフでu, v, wが互いに行き来できなければ、u, v, wは互いの最短パスの距離が同じになる。(頂点が4つ以上の場合でも同じ)

ソースコード

const int INF = 50 * 1000;
int G[55][55];
vector<int> A, B, L;
int N;
int res;
bool used[55];

int C[50 * 1000];

class Egalitarianism3 {
public:

    int maxCities(int n, vector <int> a, vector <int> b, vector <int> len) {

        if (n == 1) return 1;

        N = n;
        A = a;
        B = b;
        L = len;
        res = 1;

        memset(G, -1, sizeof(G));
        for (int i = 0; i < a.size(); i++) {
            G[a[i] - 1][b[i] - 1] = len[i];
            G[b[i] - 1][a[i] - 1] = len[i];
        }

        int res = 2;
        for (int i = 0; i < n; i++) {
            memset(used, false, sizeof(used));
            res = max(res, solve(i));
        }
        return res;
    }

    int solve(int root) {
        used[root] = true;
        vector<int> res;
        int C[55000];
        memset(C, 0, sizeof(C));
        int result = 0;
        for (int i = 0; i < N; i++) {
            if (G[root][i] == -1) continue;
            set<int> res;
            dfs(i, G[root][i], res);
            for (set<int>::iterator ite = res.begin(); ite != res.end(); ite++) {
                int l = *ite;
                C[l]++;
                result = max(result, C[l]);
            }
        }
        return result;
    }

    void dfs(int v, int len, set<int>& res) {
        res.insert(len);
        used[v] = true;
        for (int i = 0; i < N; i++) {
            if (G[v][i] == -1 || used[i]) continue;
            dfs(i, len + G[v][i], res);
        }
    }
};