2017icpc乌鲁木齐网络赛Colored Graph (构造)
2024-08-30 15:38:51
题目
https://nanti.jisuanke.com/t/16958
题意
给定一个n(n<=500)个点的无向图，给每条边黑白染色，输出同色三角形最少的个数和对应的方案
分析
首先考虑给定一个染色完毕的无向图，如何求同色三角形的个数
同色三角形的个数=总的个数-异色三角形的个数
而一个异色三角形对应两个异色角，所以我们可以通过算异色角的个数来计算异色三角形的个数
而异色角是有一个固定的点i引出去的n-1条边所决定的
设某个点i有$x_i$条1边，有$n-1-x_i$条2边
可以发现异色角的个数是$\sum {x_i*(n-1-x_i)}$
那自然我们希望每个点引出去的1边和2边数量尽可能相同
对于偶数，可以根据样例的规律构造两个n/2的团，然后对连即可
对于奇数，发现4k+1的时候边数是偶数，此时可以使得每个点两种颜色边数相同，而4k+3的时候有唯一的一个点不能满足
关于奇数的构造可以每4个点往上加，构造即可
最新文章
- springMVC学习笔记--知识点总结1
- SPSS数据分析—Probit回归模型
- [vijos P1524] 最小监视代价
- 【转】mysql如何跟踪执行的sql语句
- @SuppressWarnings—注解用法详解
- 【MySql】权限不足导致的无法连接到数据库以及权限的授予和撤销
- PHP文件下载方式
- 深入浅析mysql引擎
- CodeForces 150B- Quantity of Strings 推算..
- ab性能测试工具的使用
- Android为TV端助力:(转载)修改TextView字体样式
- MySQL创建方法错误:This function has none of DETERMINISTIC, NO SQL
- STM32F4 ------ RTC
- Nginx访问权限配置
- winform 下载
- git的入门摸索和入门研究
- 洛谷 P1757 通天之分组背包 【分组背包】
- duilib bkimage 属性
- liunx的命令大全
- 阿里云安装Oracle