题目链接
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;
}