abc282 E – Choose Two and Eat One

题意：

\(n\) 个球，第 \(i\) 个球上有数 \(a_i\)，每次操作选两个球，得到 \((a_i^{a_j} + a_j^{a_i}) \% M\) 的收益，丢弃两球之一。重复操作直到只剩一个球，问最大收益

\(n\le 500, M \le 1e9\)

思路：

\(\forall i \neq j\)，在 \(i,j\) 之间连一条边权为 \((a_i^{a_j} + a_j^{a_i}) \% M\) 的无向边。图的每棵生成树都与一种方案对应：以随便一个点为根，从下开始选边，每次丢弃儿子

跑此图的最大生成树即可

void sol() {
    cin >> n >> M;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    
    vector<array<int, 3> > edges; // weight, u, v
    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
            edges.push_back({(qmi(a[i], a[j]) + qmi(a[j], a[i])) % M, i, j});
    sort(edges.begin(), edges.end());
    reverse(edges.begin(), edges.end());
    
    iota(p, p + N, 0);
    ll ans = 0;
    for(auto [w, u, v] : edges)
        if(get(u) != get(v))
            p[get(u)] = get(v), ans += w;
    cout << ans;
}