【題解】ZeriJudge c456: 5. 馬拉松

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c456

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int maxn = 5005;

int n, m, a, b, ans, p[maxn], cnt[maxn], in[maxn];
vector <int> g[maxn], v[maxn];
queue <int> q;

int pa(int x){
    if (p[x] < 0) return x;
    else return p[x] = pa(p[x]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
        cnt[a]++;
        cnt[b]++;
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            if (cnt[j] == i){
                q.push(j);
                in[j] = 1;
            }
        }
        while (!q.empty()){
            int now = q.front();
            q.pop();
            v[i].push_back(now);
            for (auto j:g[now]){
                cnt[j]--;
                if (in[j]) continue;
                if (cnt[j] <= i){
                    q.push(j);
                    in[j] = 1;
                }
            }
        }
    }
    for (int i = n; i >= 1; i--){
        for (auto j:v[i]){
            p[j] = -1;
            for (auto k:g[j]){
                if (!p[k]) continue;
                int x = pa(j), y = pa(k);
                if (x != y){
                    if (x > y) swap(x, y);
                    p[x] += p[y];
                    p[y] = x;
                }
            }
        }
        for (int j = 1; j <= n; j++){
            if (p[j] < 0) ans = max(ans, -p[j]*i);
        }
    }
    cout << ans << "\n";
}
分享本文 Share with friends