简单的图
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Description
小明有三张简单无向图 G_1,G_2,G_3 ,其中每个图的点数均为 ,边数分别为 m_1,m_2,m_3 。
然而,小明不想带着三张图回家,只想带一张图回家,所以他用 G_1,G_2,G_3 构造一个新的无向图 。 有 个点,每个点可以表示为 (x,y,z) ,对应 中的点 , 中的点 , 中的点 。边集的构造方式如下:
-
若 中存在一条边 (u,v) ,则对于任意 1\leq a,b\leq n ,在 中添加边 ((u,a,b),(v,a,b))
-
若 中存在一条边 (u,v) ,则对于任意 1\leq a,b\leq n ,在 中添加边 ((a,u,b),(a,v,b))
-
若 中存在一条边 (u,v) ,则对于任意 1\leq a,b\leq n ,在 中添加边 ((a,b,u),(a,b,v)) 。
对于 中的任意一个点 (x,y,z) ,定义其点权为 10 。
试求 的最大权独立集的大小模 的值。
数据范围:
| n,m_1,m_2,m_3 | |
|---|---|
数据保证无自环和重边。
2025年前集训Day5(noip))-张建军(讲师)
- 状态
- 已结束
- 规则
- XCPC
- 题目
- 4
- 开始于
- 2025-1-24 8:35
- 结束于
- 2025-1-24 13:15
- 持续时间
- 4.7 小时
- 主持人
- 参赛人数
- 10