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

4 1 2
1 3
1 2

2

3 3 1
2
1 2
1 3
2 3

0

Note

For the first sample test, the graph looks like this:

Vertices 1 and 3 are special. The optimal solution is to connect vertex 4 to vertices 1 and 2. This adds a total of 2 edges. We cannot add any more edges, since vertices 1 and 3 cannot have any path between them.

For the second sample test, the graph looks like this:

We cannot add any more edges to this graph. Note that we are not allowed to add self-loops, and the graph must be simple.

Source

Codeforces Round #385 (Div. 2)

My Solution

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

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

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

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

然后把这个ci 和它所关联的点 与 所有无关键点出现的树相结合(free)，构成1个连通块，这个连通块的总边数是 (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 <iostream>
#include <cstdio>
#include <cstring>
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;
}

  Thank you!

                                                                                                                                               ------from ProLights

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠