D. 简单的图

    传统题 2000ms 1024MiB

简单的图

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

小明有三张简单无向图 G_1,G_2,G_3 ,其中每个图的点数均为 nn ,边数分别为 m_1,m_2,m_3

然而,小明不想带着三张图回家,只想带一张图回家,所以他用 G_1,G_2,G_3 构造一个新的无向图 GGGGn3n^{3} 个点,每个点可以表示为 (x,y,z) ,对应 G1G_1 中的点 xxG2G_2 中的点 yyG3G_3 中的点 zz 。边集的构造方式如下:

  1. G1G_1 中存在一条边 (u,v) ,则对于任意 1\leq a,b\leq n ,在 GG 中添加边 ((u,a,b),(v,a,b))

  2. G2G_2 中存在一条边 (u,v) ,则对于任意 1\leq a,b\leq n ,在 GG 中添加边 ((a,u,b),(a,v,b))

  3. G3G_3 中存在一条边 (u,v) ,则对于任意 1\leq a,b\leq n ,在 GG 中添加边 ((a,b,u),(a,b,v))

对于 GG 中的任意一个点 (x,y,z) ,定义其点权为 1018(x+y+z)^{18(x+y+z)}

试求 GG 的最大权独立集的大小模 998244353998244353 的值。

数据范围:

n,m_1,m_2,m_3
141\sim 4 100\le 100
5105\sim 10 105\le 10^5

数据保证无自环和重边。

2025年前集训Day5(noip))-张建军(讲师)

未参加
状态
已结束
规则
XCPC
题目
4
开始于
2025-1-24 8:35
结束于
2025-1-24 13:15
持续时间
4.7 小时
主持人
参赛人数
10