Codeforces Round #711 Two Houses 图论

题意

这是一道交互式的题目。你输出完了他才给你下一次输入。

有一张点数为$n$的有向图。只给你这张图每个点的入度。

这张图里面的任意两点$A$和$B$之间有且仅有一条有向边。目标是找到两个点,使得这两个点在一个环中,且入度差的绝对值尽可能大。

现在,你可以输出任意次不重复查询。每次输出两个点,$A$和$B$。然后他就告诉给你$A$到$B$是否能通。任意一次查询,如果查出来的结果是能通,就不能再有任何查询。

在查询结束之后,你要输出目标要求的两个点。如果整个图没有环,则输出0 0。

题解

先说结论。对于所有可能的两个点的配对($\frac{n\times(n-1)}{2}$种可能)的入度差的绝对值进行从大到小排序。依次查询这些配对中入度大的到入度小的的点的连通性。如果能联通,则这两个点满足条件。

看一眼下面这张图就很明显了:

A比B的入度高。且能联通到B。

我们可以看到,在$B$的所有出度的点中必然至少有一个点是$A$的入度。因此只要入度更大的点能通较小的点就必定成环。

对于入度相等的两个点,其实也是一样。因为$A$到$B$能通会分别占用各自一个出度和一个入度。

代码

Submission #113086430 - Codeforces
Codeforces. Programming competitions and contests, programming community