B. Party

Party"/>

B. Party

题面

分析

可以发现只需要保留最大的偶数条关系，假如 m m m本身就是偶数，那么答案一定是0，如果 m m m不是偶数，把么就需要减去奇数条关系使剩余关系变成偶数条，那么第一种方法，可以减去某一个人，这个人的朋友有奇数个，减去这个人也就意味着减去奇数条关系；第二种方法，可以减去一对朋友，这一对朋友必须满足都有奇数个朋友，因为，减去这一对朋友中的其中一个后，会减少偶数条关系，但是此时剩余的朋友由于失去了和减去的朋友的那一条关系，那么他还剩奇数条关系，在减去他也就相当于减去了奇数条关系，也可以得到答案，最后将两种情况所有情况取最小值就可以了。

代码

#include <bits/stdc++.h>using namespace std;
using ll = long long;void solve() {int n, m;cin >> n >> m;vector<int> a(n + 1);vector<int> u(m), v(m);vector<int> cnt(n + 1);for(int i = 1; i <= n; i ++) cin >> a[i];for(int i = 0; i < m; i ++) {cin >> u[i] >> v[i];cnt[u[i]] ++;cnt[v[i]] ++;}if(m % 2 == 0) {cout << 0 << "\n";return ;}int ans = 1e9;for(int i = 1; i <= n; i ++) {if(cnt[i] & 1) {ans = min(ans, a[i]);}}for(int i = 0; i < m; i ++) {if(cnt[u[i]] % 2 == 0 && cnt[v[i]] % 2 == 0) {ans = min(ans, a[u[i]] + a[v[i]]);}}cout << ans << "\n";
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while(T --) {solve();}
}