Codeforces Round #318 (Div. 2), problem: (B) Bear and Three Musketeers 【暴力】
发布日期:2021-06-29 14:29:27
浏览次数:2
分类:技术文章
本文共 893 字,大约阅读时间需要 2 分钟。
题意
在一个无向图中求一个三元环与外界最小连接边的数量
思路
数据正好,我们考虑枚举一条边,那么这条边的两端就确定了,再枚举一个点,那么判断该点是否和边的两个端点相连,如果是的情况下,我们统计每个点的入度,每次取最小值。
因为是三元环,每个点的内度,也就是每个点必须和其他两个点相连,是2*3=6,最后用总度数减6就是最后答案。
code
#include#define endl '\n'using namespace std;const int maxn=5e3+5;int vis[maxn][maxn];int n,m;int in[maxn];int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; for(int i=0;i >u>>v; in[u]++,in[v]++; vis[u][v]=vis[v][u]=1; } int ans=0x3f3f3f3f; int flag=0; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(vis[i][j]){ for(int k=j+1;k<=n;k++){ if(vis[i][k]&&vis[k][j]){ ans=min(ans,in[i]+in[j]+in[k]); flag=1; } } } } } if(flag) cout< <
学如逆水行舟,不进则退
转载地址:https://chocolate.blog.csdn.net/article/details/104142063 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年04月25日 04时13分49秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
今日芯声 | 连发五个“感恩”,余承东庆祝与鸿蒙OS同一天生日
2019-04-29
对照检查!高效程序员几乎都有这七项技能
2019-04-29
远离“骗子综合症”,这六个习惯助你进阶真正高手
2019-04-29
当机器能承载所有回忆,你是就此沉溺,还是无虑向前?
2019-04-29
想让AI变现?这六大市场营销场景不容忽视
2019-04-29
前方恶臭警告!拯救代码,你需要这套强化攻略
2019-04-29
IBM PowerAI Vision:极速创建计算机视觉应用程序
2019-04-29
效率提升80%!最好的反欺诈系统之一面世
2019-04-29
外科医生就是男性?算法为何也有性别歧视
2019-04-29
修改变量名,简单有效地提高代码质量!
2019-04-29
代码详解:一文掌握神经网络超参数调优
2019-04-29
Keras VS PyTorch,总有一个理由让你选择它们
2019-04-29
数据科学家常犯的十大编码错误
2019-04-29
让开发人员变平庸的八个习惯,看看你中了几条
2019-04-29
JavaScript数组方法三板斧,100%的开发都得知道
2019-04-29
当SQL不管用时,“noSQL运动”兴起了……
2019-04-29
为何说数据映射是数据集成任务的第一步?
2019-04-29
海量样本无从下手?这五种抽样算法分分钟搞定
2019-04-29
九大人工智能发展趋势,助你一窥未来
2019-04-29
高性能数据架构是数字化发展的首要任务吗?
2019-04-29