CF1711B题解

__vector__ · 2022-07-25 01:19:15 · 个人记录

解法

• 也就是说所有的数都可以选，输出 $0$。
• 也就是说要选择一些数删掉，使得**自己选择的数列中**出现的好友对数数量为偶数个。 考虑将两个好友连边。如果一个结点的度数为奇数，将其删掉之后将会破坏掉奇数对好友，剩下偶数对好友。 另外，如果两个好友节点的度数都为偶数，那么将两个好友节点一起删掉，也将会破坏掉奇数对好友，剩下偶数对好友。 所以，对这两种情况进行判断，取最小花费即可。

Code

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    const int maxn=1e5+5;
    int t;
    int n,m;
    struct Peo
    {
        int id,a;
    }peo[maxn];
    vector<int> fri[maxn];
    void main()
    {
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++)
            {
                fri[i].clear();
                scanf("%d",&peo[i].a);
                peo[i].id=i;
            }
            int x,y;
            for(int i=1;i<=m;i++)
            {
                scanf("%d%d",&x,&y);
                fri[x].emplace_back(y);
                fri[y].emplace_back(x);
            }
            if(m%2==0)
            {
                printf("0\n");
                continue;
            }
            int ans=0x3f3f3f3f;
            for(int i=1;i<=n;i++)
            {
                if(fri[peo[i].id].size()%2!=0)
                {
                    ans=min(ans,peo[i].a);
                }
            }
            for(int i=1;i<=n;i++)
            {
                for(int j=0;j<fri[i].size();j++)
                {
                    if(fri[i].size()%2==0&&fri[fri[i][j]].size()%2==0)
                    {
                        ans=min(ans,peo[i].a+peo[fri[i][j]].a);
                    }
                }
            }
            printf("%d\n",ans);
        }
    }
}
int main()
{
    Main::main();
    return 0;
}