题面
分析
可以发现只需要保留最大的偶数条关系,假如 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();
}
}