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

题目 参考

题意

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

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

思路

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

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

有两种情况

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

代码

#include 
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