这是一道交互题

定义二分图为一种可以将点集$V$划分为$S$和$T$的图，满足条件：

• $1.S\cup T=V，S\cap T=\Phi$
• $2.\mathrm{对}\mathrm{于}\mathrm{所}\mathrm{有}(x,y)\in E，\mathrm{有}x\in S，y\in T\mathrm{或}x\in T，y\in S$

你也可以选择百度来帮助理解二分图的定义。

定义二分图的一个$k$划分方案为将二分图中每一条边染任意一种$1$到$k$之间的颜色的方案。

定义在二分图的一种$k$划分方案中$w_{ij}$表示经过第$i$个点的颜色为$j$的边的条数。

定义在二分图的一种$k$划分方案中节点$i$的不平均度为$ma{x}_{w_{ij}}-mi{n}_{w_{ij}},j\in [1,k]$。

定义二分图的一种$k$划分方案中的不平均度为所有节点的不平均度之和。

题目描述

给定一个$S$,$T$中各有$n$个点的二分图。

其中点的编号为$1,\dots ,n$。

初始时候二分图内没有任何一条边,也就是$V=\Phi$。

你需要动态支持向图中加边，删边。

同时求出任意一个不均匀度最小的$k$划分方案。

注意，在本题中$S$集合和$T$集合中的点不会随着图改变，也就是说,$S$集合和$T$集合在同一个问题(测试点)中是不变的。

任务介绍

你需要实现两个函数Init和Modify。

• Init(n,k,Q)

  • n,k含义见题目描述。
  • Q为操作的个数。
  • 你不需要返回任何值。

在每个测试点中，交互库都会调用恰好一次Init函数。

• Modify(x,y)

  • x,y是两个$1,\dots ,n$的数。
  • 该函数改变连接$S$集合中第$x$个点到$T$集合中第$y$个点的边的存在性。
  • 你需要返回在改变存在性之后的任意一种$k$划分方案。

在每个测试点中，交互库都会调用恰好$Q$次Modify函数。

由于检验时间非常大，实际测评时候SPJ仅仅会纯随机检测$min(Q,50000)$个方案的正确性。如果对于选出的min(Q,50000)个方案都最优则算AC。但是选手仍然需要返回所有操作之后的答案因为没有人可以确定这个方案是否会被检测。即使同一个程序的不同提交检测的也是不同的操作之后的方案。这个机制只会被用于加速测评，请不要使用这个机制骗取AC。

由于某些特殊原因，下发SPJ不支持随机检测。

实现方法

本题只支持C++。

源代码中需要包含头文件graph.h。

你需要实现的函数的相关接口:

void Init(int n,int k,int Q);
Division Modify(int x,int y);

其中division定义如下

struct Division{int color[22][22];};

其中$colo{r}_{ij}$表示$S$集合中的第$i$个节点到$T$集合中的第$j$个节点的边的颜色。

对于不存在那一条边，则该元素值必须为0.

如何测试你的程序

你需要在本题目录下使用如下命令编译得到可执行程序：

g++ -o graph grader.cpp graph.cpp -O2

可执行文件将从标准输入读取以下格式的数据：

第一行包含一个正整数$seed$，需要保证$0\le seed\le 2^{30}-1$。 * 为方便选手调试，在$seed$为零时数据不会进行加密。

第二行一共三个正整数，$n,k,Q$，需要保证$2\le k\le n\le 20,1\le Q\le 500000$。

读入完成之后，交互库将会调用Init函数。

接下来$Q$行，一行两个整数$x,y$。需要保证$1\le x,y\le n$

每一行读入完成之后，交互库会调用Modify函数

交互库将会在标准输出中输出以下信息：

每一次调用完Modify函数后，交互库都会输出一行形如Count: cnt的输出，其中cnt为你的方案的不平均度。 * 如果你给出的方案不合法的话cnt会等于 -1。

注意最终测评时使用的$grader$和下发的$grader$不同

样例源代码

在本题目录下，有C++语言的样例源代码graph.cpp。按照上文中提到的方式进行编译，即能通过编译得到可执行程序。

样例源代码只是帮助理解题目，结果一定不正确。

限制与约定

对于所有数据，满足$2\le n,k,1\le Q$

时间限制：$\mathtt{\text{1s}}$

空间限制：$\mathtt{\text{512MB}}$

题目中所给的时间、空间限制为你的代码和交互库加起来可以使用的时间和空间。我们保证，对于任何合法的数据，任何版本的交互库（包括下发给选手的和最终评测使用的），在检验次数不超过50000次的情况下，在OJ上运行所用的时间不会超过0.5s，运行所用的空间不会超过12MB，也就是说，选手实际可用的时间至少为0.5s，实际可用的空间至少为500MB。

交互式类型的题目怎么本地测试

下载

交互库下载