CF1711B Party
原题题意
给定 $n$ 个点带点权的无向图，点权 $a_i$ 保证无重边自环，点权非负），要求删去一些点和它相连的边，使得剩下这个图的边数为偶数且删去点的点权之和最小。问删去点的点权之和最小是多少？
分类讨论
我们分类讨论一下。
-
$m$ 为偶数，则不需要删边或点，直接输出 $0$ 即可。
-
$m$ 为奇数，我们称有单数条边与其相连的点为单点，反之为双点。
- 删除一个点，则必须为单点（奇-偶=奇 奇-奇=偶）
- 删除两个点，若两点中有单点，则直接删除单点更优，所以应当删除两个双点；因为需要删除的总边数为单数，所以删除的双点应该有公共边：故删除一条边相连的两个双点满足题意。
- 删除三个点，不如删除一个或两个更优，故不考虑。
代码及注释
/*code by Cheemsadoge*/
#include <bits/stdc++.h>
using namespace std;
template<typename T> inline void read(T &x) {
x=0;T w=1,ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
x=x*w;
}//fast input
const int MAXN=1e5+1145;
const int INF=2147483647ll;//2^31-1
struct Edge{int u,v;}edge[MAXN]; //边，u、v分别表示边相连的两点
struct Point{int val,stick,num;}point[MAXN]; //点，val表示边权（即不快乐值），stick表示与点所连的边数，num表示编号
int n,m,totr,ans=INF,wans=INF,num,a,b;
bool single[MAXN]; //判断i与i点所连的边数是否为单（是则赋值true）->single[i]即point[i].stick%2==1
void add_edge(int u,int v){edge[++totr].u=u;edge[totr].v=v;point[v].stick++;point[u].stick++;} //加边
queue<Point>po;
void initialize()//初始化
{
totr=0;ans=INF;wans=INF;
memset(edge,0,sizeof(edge));
memset(point,0,sizeof(point));
memset(single,0,sizeof(single));
}
int main() {
Point u;
int T;read(T);while(T--){
initialize();
read(n),read(m); read(n),read(m);
initialize();
for(int i=1;i<=n;i++) read(point[i].val),point[i].num=i,po.push(point[i]);//暂时将点放入po队列，方便取用
for(int i=1;i<=m;i++) read(a),read(b),add_edge(a,b);//加边
if(m%2==0) {printf("0\n");continue;}//特判：若有偶数条边，则输出0.注意：不要把此句放在上两行前，否则会跳过输入
while(!po.empty()){
num=po.front().num;u=point[num];//等同于u=po.front;
if(u.stick%2) {ans=min(ans,u.val);single[u.num]=1;}//判断与点相连的边数是否为单，并将其中点权最小值存入ans
po.pop();
}
for(int i=1;i<=m;i++) if((!single[edge[i].v])&&(!single[edge[i].u])) wans=min(wans,point[edge[i].u].val+point[edge[i].v].val);
//枚举边，若所连两点的stick为复数，则将两点点权相加存入wans取最小
printf("%d\n",min(ans,wans));//输出最小值
}
}