Codeforces Round 810 (Div. 2) B. Party（图论）

本文主要是介绍Codeforces Round 810 (Div. 2) B. Party（图论），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

某俱乐部计划举办一次聚会，并将邀请部分 $n$ 成员参加。 $n$ 名会员的编号为 $1, 2, \dots, n$ 。如果不邀请成员 $i$ ，聚会的不快乐值将为 $a_i$ 。

在 $n$ 位成员中，有 $m$ 对朋友。按照传统，如果一对朋友中的两个人都被邀请，他们将在聚会上分享一个蛋糕。吃掉的蛋糕总数将等这两个成员都被邀请的朋友对数。

但是，俱乐部的烤箱一次只能烤两个蛋糕。因此，俱乐部要求吃掉的蛋糕总数是偶数。

在遵守吃掉的蛋糕总数是偶数这一限制条件的情况下，该聚会可能的总不快乐值最小是多少？

输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $t ( 1≤t≤10^4 )$ 。测试用例说明如下。

每个测试用例的第一行包含两个整数 $n$ 和 $0≤m≤min(10^5,\frac{n(n−1)}{2} )$ –俱乐部成员人数和朋友对数。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,…,a_n ( 0≤a_i≤10^4 )$ –不快乐值数组。

接下来的每行 $m$ 都包含两个整数 $x$ 和 $y (1 \leq x, y \leq n ， x \neq = y)$ ，表示 $x$ 和 $y$ 是好友。每个无序对 $(x, y)$ 在每个测试用例中最多出现一次。

可以保证所有测试用例中 $n$ 和 $m$ 的总和不超过 $10^5$ 。

输出
为每个测试用例打印一行，其中包含一个整数–有效方的最小可能不快乐值。

要求最小不快乐值，那么就是让尽可能少的人不被邀请，并且满足题目条件中的朋友对数为偶数。

那么没有朋友的人全部都要邀请。

现在给出的朋友对数，我们就可以将所有有朋友的人当作点，而朋友关系就是边，现在我们要进行删除某些点的操作来使得边的数量为偶数个。
那么我们现在只要是让边数为偶数就可以满足题目条件。

考虑两种情况：

第一种情况：当前朋友对数已经是偶数个，那么就不需要删除任何任何边，所以我们可以邀请上所有人，这个情况下不快乐值是0。
第二种情况：当前朋友对数是奇数个，这时候我们标记上所有点的度数，即某个点和几个边相连度数就是几。

这时候有两种删法，可以删掉度数相加为偶数的两个相连的点，也可以删掉度数为奇数的一个点。

度数相加为偶数的两个相连的点意味着砍掉了奇数条边，首先删掉这两个点的时候这两个点之间的边就会被删掉，这时候删掉了1条边，两点相加度数为偶数，度数同时减一就导致两点向外延伸的被砍掉的边依旧是偶数个，所以最终一定会砍掉奇数条边，那么就可以使得最终边数为偶数。

删掉度数为奇数的一个点就是砍掉奇数条边。

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
#define int long long
#define endl '\n'vector<int>e[N];
int n,m;
int a[N];
int degree[N];void solve(){cin >> n >> m;for(int i = 1;i <= n;i++)cin >> a[i];if(m & 1){  //奇数while(m--){int x,y;cin >> x >> y;degree[x]++;degree[y]++;e[x].push_back(y);}//删除单点int res = 2e9;for(int i = 1;i <= n;i++){if(degree[i] & 1){res = min(res,a[i]);}}//删除双点for(int i = 1;i <= n;i++){for(auto j : e[i]){if(((degree[i] + degree[j])&1) == 0){res = min(res,a[i] + a[j]);}}}cout << res << endl;}else{      //偶数while(m--){int x,y;cin >> x >> y;}cout << 0 << endl;           }for(int i = 1;i <= n;i++){degree[i] = 0;e[i].clear();}
}signed main(){int T;cin >> T;while(T--){solve();}return 0;
}