题目链接

https://codeforces.com/gym/102769/problem/F

题目大意

教授有$n$个好学生,想带其中一些参加一个会议(也可以谁都不带)。这些学生中有一些同学是好友关系,如果他们之中只有一个人去,小组的友好度会$-1$,如果他们都去,友好度会$+1$,此外,如果有有$k$个学生参加会议,小组友好度会$-k$,题目要求输出小组最高友好度。

思路

对于一个连通子集,如果其$\sum degree\geq 2 *|V|$,那么选择这些顶点不会使答案更劣。遍历整张图,找出满足上述性质的连通子集,答案即为$\sum degree-k$。

注意题目测试组数很多,不能每一次都开一个1e5数量级的数组并清空,否则可能会因为内存操作导致超时。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 1;

int t;
int n, m;
int ans;

pair<int, int> dfs(int x, int* deg, int* vis, vector<int> *G) {
    vis[x] = true;
    int cur_deg = deg[x];
    int vertex_n = 1;

    for ( auto nxt : G[x] ) 
        if ( !vis[nxt] ) {
            pair<int, int> result = dfs(nxt, deg, vis, G);
            cur_deg += result.first;
            vertex_n += result.second;
        }

    return {cur_deg, vertex_n};
}

int main() {
    scanf("%d", &t);

    for ( int T = 1; T <= t; ++T ) {
        printf("Case #%d: ", T);

        scanf("%d%d", &n, &m);

        int deg[n + 1];
        int vis[n + 1];
        memset(deg, 0, sizeof deg);
        memset(vis, 0, sizeof vis);
        vector<int> G[n + 1];

        int u, v;
        for ( int i = 1; i <= m; ++i ) {
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
            ++deg[u];
            ++deg[v];
        }

        for ( int i = 1;  i <= n; ++i ) 
            if ( !vis[i] ) {
                pair<int, int> result = dfs(i, deg, vis, G);
                if ( result.first >= result.second * 2 )
                    ans += result.first / 2 - result.second;
            }

        printf("%d\n", ans);

        ans = 0;
    }

    return 0;
}
Last modification:October 21, 2020
博客维护不易,如果你觉得我的文章有用,请随意赞赏