Codeforces Round #385 (Div. 2) C. Hongcow Builds A Nation 并查集+贪心+组合学、图论、dfs

My Solution

题意：有n个点(其中有k个关键点)，m条边，要求添加尽可能多的边使得k个关键点之间没有路径，问最多可以添加多少条边。

并查集+贪心+组合学、图论、dfs

用并查集处理这个图，相关联的点构成一颗树，然后把每棵树的结点数储存在该树的根节点上，

然后开始贪心，找出k个关键点里，关键点所在树的结点个数最多的结点 maxci，

然后把这个ci 以及它所关联的点 与 所有没有关键点出现的树相结合(free)，形成一个连通块，这个连通块的总边数是 (free + maxcnt) * (free + maxcnt - 1) / 2;

然后剩下的是除了这个maxci之外的有关键点的树，这些树储存的点构成完全图的边数是 if(i != maxci)  ans += cnt[_find(c[i])] * (cnt[_find(c[i])] - 1) / 2;

所有得到的ans 是满足条件时的图的总边数，减点输入的m条边， ans - m 即为在合理的情况下可以添加的最大边数

复杂度 O(n^2)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e3 + 8;

//有时可能需要 并查集+离散化
int father[maxn], _rank[maxn];
inline void DisjointSet(int n)
{
    for(int i = 0; i <= n; i++){
        father[i] = i;
    }
}

inline int _find(int v)
{
    return father[v] = father[v] == v ? v : _find(father[v]);
    //同时压缩路径，有时不能压缩路径，有时必须压缩路径，看具体情况
}

inline void _merge(int x, int y)
{
    int a = _find(x), b = _find(y);                //
    if(_rank[a] < _rank[b]){ father[a] = b; } else{ father[b] = a; if(_rank[a] == _rank[b]){ _rank[a]++; } } } LL c[maxn], cnt[maxn], maxci; bool flag[maxn]; int main() { #ifdef LOCAL freopen("d.txt", "r", stdin); //freopen("d.out", "w", stdout); int T = 4; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int n, m, k, u, v; cin >> n >> m >> k;
    for(int i = 0; i < k; i++){ cin >> c[i];
    }
    DisjointSet(n);
    for(int i = 0; i < m; i++){ cin >> u >> v;
        if(_find(u) != _find(v)) _merge(u, v);
    }

    for(int i = 1; i <= n; i++){
        cnt[_find(i)]++;
    }
    LL maxcnt = 0;
    for(int i = 0; i < k; i++){
        if(maxcnt < cnt[_find(c[i])]){
            maxcnt = cnt[_find(c[i])];
            maxci = i;
        }
        flag[_find(c[i])] = true;
    }
    LL free = 0;
    for(int i = 1; i <= n; i++){
        if(!flag[i]){
            free += cnt[i];
        }
    }

    LL ans = (free + maxcnt) * (free + maxcnt - 1) / 2;
    for(int i = 0; i < k; i++){
        if(i != maxci){
            ans += cnt[_find(c[i])] * (cnt[_find(c[i])] - 1) / 2;
        }
    }

    cout << ans - m << endl;

    #ifdef LOCAL
    memset(flag, false, sizeof flag);
    memset(cnt, 0, sizeof cnt);
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx