B. Party（图论/暴力/顶点的度数）

题目
参考

题意

有n个人，m对朋友关系。
举办聚会，邀请若干人，使得被邀请的人中，是朋友关系的有偶数对。
每个人有个开心值a[i]，如果第i个人没有被邀请，会获得a[i]的不开心值。

问怎么邀请，使总得不开心值最小。

思路

如果m是偶数，此时全部邀请即可，不开心值为0
以下考虑m是奇数的场景。

我们将每个人看做顶点，朋友关系看作边。
问题转化成，从这图中，删除若干顶点，使得剩余的图，边数为偶数。

有两种情况

• 删除度数为奇数的顶点，此时只需删一个。
• 删除度数为偶数的顶点，此时需要删除两个相邻顶点。

代码

#include<bits/stdc++.h> 
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int maxn = 200010;

int n, m;
int a[maxn], degree[maxn];
int x[maxn], y[maxn];
void solve() {
    
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
    
		scanf("%d", &a[i]);
		degree[i] = 0;
	}
	for (int i = 1; i <= m; ++i) {
    
		scanf("%d%d", &x[i], &y[i]);
		++degree[x[i]];
		++degree[y[i]];
	}
	int ans = inf;
	// 1. m is even
	if (m % 2 == 0) {
    
		ans = 0;
	}
	// 2. m is odd
	
	// 2.1 delete i where degree[i] is odd.
	for (int i = 1; i <= n; ++i) {
    
		if (degree[i] & 1) {
    
			ans = min(ans, a[i]);
		}
	}
	
	// 2.2 delete neighbor x, y where degree[x],degree[y] is even
	for (int i = 1; i <= m; ++i) {
    
		if (degree[x[i]] % 2 == 0 && degree[y[i]] % 2 == 0) {
    
			ans = min(ans, a[x[i]] + a[y[i]]);
		}
	}
	
	printf("%d\n", ans);
	
}
int main() {
    
	int t;
	scanf("%d", &t);
// t = 1;
	while (t--) {
    
		solve();
	}
}

最后

weixin gongzhonghao搜 对方正在debug，关注下，一起快乐刷题吧