题解 | #小欧皇#

并查集

使用并查集维护维护当前状态下联通块的大小。

建图的时候只考虑会有影响的边。

每个联通块的收益值是 $C_n^2$
首先计算当前状态下的收益值
对于每个可能占领的城市，我们计算收益的增加值

遍历每个可能的连通块

初始的时候我们新的城市算一个联通块大小为1，假设遍历的第一个连通块大小为 $k_1$

则此时增量为 $C_{{k_1} add {1}}^2 - C_1^2 - C_{k_1}^2$

依此类推 $C_{{k_2} add {k_1} plus {1}}^2 - C_{{k_1} add {1}}^2 - C_{k_2}^2$

#include <iostream>
#include <vector>
using namespace std;
const int maxn = 1e5 +10;
vector<int> f(maxn);
vector<int> v(maxn);
vector<vector<int>> g(maxn);
vector<int> vis(maxn,0);
int find(int p ){
    if (f[p] == p) 
        return p;
    return f[p] = find(f[p]);
}
void merge(int x,int y){
    int p = find(x);
    int q = find(y);
    if(p != q){
        f[p] = q;
        v[q] = v[p] + v[q];
    }
}
void zero(int n){
    for (int i = 0 ; i < n + 1 ; i++) vis[i] = 0;
}
int main() {
    int n,m;
    string s;
    cin >> n >> m  >> s;
    for (int i = 0 ; i < n + 1 ; i++) v[i] = 1,f[i] = i;//初始化并查集状态
    long long ans = 0;
    int re = -1;
    int tmp = 0;
    while(m--){
        int x,y;
        cin >> x >> y;
        if(s[x - 1] == '1' && s[y - 1] == '1'){
            merge(x,y);
        }
        else if(s[x - 1] == '0' && s[y - 1] == '1'){
            g[x].push_back(y);
        }
        else if(s[x - 1] == '1' && s[y - 1] == '0'){
            g[y].push_back(x);
        }
    }
    //计算原有的收益
    for (int i = 0 ; i < n ; i++){
        if(s[i] == '1'){
            int k = find(i+1);
            if(vis[k] == 0){
                int sum = v[k];
                ans += 1ll * sum * (sum - 1) / 2;
                vis[k] = 1;
            }
            
        }
        if(re == -1 && s[i] == '0'){//如果占领的每个城市都与原来占领的城市没有连接，会出错
            re = i + 1;
        }
    }
    zero(n);
    for (int i = 0 ; i < n ; i++)   {
      //计算新***市的收益
        if(s[i] == '0' && g[i+1].size() > 0){
            long long  key = 1;
            long long tmpp = 0;
            for (auto &zz : g[i+1]){
                // cout << zz <<" " <<i+1 << find(zz) <<endl;
                int zzz = find(zz);
                if(vis[zzz] == 0){
                    tmpp += (key + v[zzz]) * (key + v[zzz] - 1) / 2 -  key * (key - 1) / 2 -  v[zzz] * (v[zzz] - 1) / 2;
                    // cout << tmpp << endl;
                    key += v[zzz];
                    vis[zzz] = 1;
                }
            
            }
            // tmpp += key;
            if( tmp < tmpp){
                tmp = tmpp;
                re = i + 1;
            }
            zero(n);
        }
    }
    // cout << ans << endl;
    cout << re << " " << ans + tmp << endl;

    return 0;
}
// 64 位输出请用 printf("%lld")