作者：彼岸花芬芳 | 来源：互联网 | 2023-05-18 18:51
题目链接https:codeforces.comproblemsetproblem1711Bhttps:www.luogu.com.cnproblemCF1711B题意简述一个俱乐
题目链接
https://codeforces.com/problemset/problem/1711/B
https://www.luogu.com.cn/problem/CF1711B
题意简述
一个俱乐部计划举办一次聚会，并邀请 \(n\) 名会员中的一些人。\(n\) 名成员分别由数字 \(1,2,...,n\) 表示。如果成员 \(i\) 没有被邀请，团队将获得 \(a_i\) 的不快乐值。
\(n\) 名成员中有 \(m\) 对好友。按照惯例，如果邀请了一对好友，他们会在聚会上分享蛋糕。被吃掉蛋糕的总数将等于两名成员都被邀请的好友的对数。
然而，俱乐部的烤箱一次只能烤两个蛋糕。因此，俱乐部要求吃掉的蛋糕总数是偶数。
考虑到被吃掉的蛋糕总数为偶数的约束条件 , 聚会的最低的总不快乐值是多少？
样例
点击查看样例
分析
如果 \(a\) \(b\) \(c\) 三个人去参加, \(a\) 和 \(b\) 是朋友, \(b\) 和 \(c\) 是朋友 ,\(a\) 和 \(c\) 也是朋友,那他们将会吃掉三块蛋糕
对于样例3,他们的朋友关系如图所示
肯定是参加的人越多越是最优解,所以我们要尽量少的删掉人
如果朋友关系的个数是偶数(反映到图中就是边的数量),他们恰好吃偶数块蛋糕,所以都可以参加.不开心值为0
如果朋友关系的个数是奇数,即有奇数条边,我们需要删掉某些点来保证边的数量为偶数.
方法有二:
①删掉一个度数为奇数的点
②删掉两个相邻的度数为偶数的点.因为度 \(a\) 和 度 \(b\) 都是偶数,把他俩删掉,边的个数会少 度 \(a\) + 度 \(b\) \(- 1\) 条 \((\) \(因为有一条公共边被算了两次\) , \(故减\) \(1\) \()\)
读入朋友关系的同时记录每个点的度,对于没有在所列朋友关系中的点我们都不需要考虑它的情况,因此可以直接根据朋友关系来遍历图而不需要真的建图
点击查看代码
#include
using namespace std;
const int N=1e5+10;
int a[N];
int x[N];
int y[N];
int d[N];
int main()
{
//freopen("uva.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
memset(d,0,sizeof d);
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x[i],&y[i]);
d[x[i]]++;
d[y[i]]++;
}
if(m%2==0)
{
printf("0\n");//朋友关系有偶数个,所有人来都可以.
}
else
{
int ans=2147483647;
for(int i=1;i<=m;i++)
{
if(d[x[i]]%2!=0)
{
ans=min(ans,a[x[i]]);
}
if(d[y[i]]%2!=0)
{
ans=min(ans,a[y[i]]);
}
if(d[x[i]]%2==0&&d[y[i]]%2==0)
{
ans=min(ans,a[x[i]]+a[y[i]]);
}
}
printf("%d\n",ans);
}
}
return 0;
}
![python的交互模式怎么输出名文汉字[python常见问题]](https://img1.php1.cn/3cd4a/24cea/978/9f39a0b333a15215.gif)
京公网安备 11010802041100号