Skip to content

CF1498E Two Houses

原题链接：E. Two Houses

Tag：交互、图论。

题目描述

有一张含有 \(n\) 个点的完全图， 每两个点之间有且只有一条有向边。

给出 \(n\) 以及每一个点的入度 \(k_i\)。 要求找出两个点 \(A,B\)， 这两个点双向连通，同时 \(\vert k_A - k_B \vert\) 最大。

交互过程是使用 ? a b 询问 \(a\) 是否能到达 \(b\)， 此题无交互次数限制，但是一旦询问到了 \(Yes\) 必须直接进行回答。

回答格式为 ! a b ，若不存在答案输出 ! 0 0。

数据说明：

\(3 \leq n \leq 500\)

分析

解法一

首先这个给定的图是一张竞赛图， 讨论的是竞赛图上的连通性问题。

看到双向连通很容易想到强连通分量， 于是这里存在一个性质：

竞赛图在经过强连通分量缩点之后呈现出来一种"链状“。 这种链不是传统意义上的链，而是如图所示：

img.png

观察缩点之后的拓扑序， 如果将拓扑序小的放在左边， 拓扑序大的放在右边，这样排成一条链之后不难发现： 拓扑序小的一定能到达拓扑序大的强连通分量， 并且拓扑序大的强连通分量的入度一定严格大于拓扑序小的强连通分量。

根据上述发现可以进一步推出：出度大的一定能到达出度小的。

而由于图是一张竞赛图，满足 \(入度+出度=n-1\)。 于是可以把上述推论变成：入度小的一定能到达入度大的。

于是我们已经可以根据这个题输入的入度来判断某些点之间的单向到达了， 我们可以通过交互操作来找出是否双向可达。

由于要保证 \(\vert k_A - k_B \vert\) 最大， 我们存 \(n^2\) 组点对，按照 \(\vert k_A - k_B \vert\) 排序， 每次找最大的一组点，由于入度小的一定可以到达入度大的， 我们只需要询问这一组点中入度较大的能否到达入度小的即可。 一旦交互返回了 \(Yes\)，答案就是当前询问的一组点， 如果一直没有收到 \(Yes\) 的反馈则无解，输出! 0 0。

以上解法复杂度为 \(O(n^2)\)

解法二

在有了上述的结论之后， 我们考虑从拓扑序较小的地方开始观察， 发现对于第 \(1\) 个到第 \(i\) 个强连通分量， 这些强连通分量的入度的和为 \(i * (i - 1) / 2\)， 因为这一部分是一个首项为 \(0\) 公差为 \(1\) 的等差数列。

所以我们从入度最小的点开始统计总共的入度，记为 \(sum\)。 每当我们发现记录的 \(sum\) 为 \(i * (i - 1) / 2\) 的时候， 就可以确定第 \(1\) 到第 \(i\) 个点组成了这个竞赛图中拓扑序最小的若干个强连通分量。

经过上述的操作我们可以在线性的时间内根据题目给出的入度处理出所有的强连通分量。

综上所述，如果使用桶排序的话时间复杂度可以达到 \(O(n)\)， 但是由于 \(n\) 的范围只有 \(500\)，性能差异并不明显。

除此之外，以上做法无需进行交互操作。

代码实现

解法一（577ms）

void NeverSayNever() {
    int n; cin >> n;
    vector<int> vec(n+1);
    for (int i = 1; i <= n ; ++i) {
        cin >> vec[i];
    }
    vector<PII> tmp;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n ; ++j) {
            tmp.push_back(make_pair(i,j));
        }
    }
    std::sort(tmp.begin(), tmp.end(),[&](PII x,PII y){
        return abs(vec[x.first] - vec[x.second]) > abs(vec[y.first] - vec[y.second]);
    });
    for(int i = 0; i < tmp.size();i++){
        auto &[u,v] = tmp[i];
        if(vec[v] > vec[u]) {
            cout << '?' << ' ' << v << ' ' << u << endl;
        }else{
            cout << '?' << ' ' << u << ' ' << v << endl;
        }
        cout.flush();
        string res; cin >> res;
        cout.flush();
        if(res == "Yes"){
            cout << '!' << ' ' << u << ' ' << v << endl;
            cout.flush();
            return;
        }
    }
    cout << '!' << ' ' << 0 << ' ' << 0 << endl;
    cout.flush();
    return;
}

解法二（77ms）

可以通过把排序换成桶排序来实现真正的 \(O(n)\)， 但是测完发现速度倒退，感兴趣的可以自己实现， 因为我桶排写的不是很美观所以放了使用 \(sort\) 的代码。 

void NeverSayNever() {
    int n; cin >> n;
    vector<PII> vec(n+1);
    for (int i = 1; i <= n ; ++i) {
        cin >> vec[i].first;
        vec[i].second = i;
    }
    std::sort(vec.begin(), vec.end());
    int sum = 0;
    int p = 1;
    int mx = -1;
    PII ans(0,0);
    for (int i = 1; i <= n ; ++i) {
        sum += vec[i].first;
        if(sum == i * (i - 1) / 2){
            if(vec[i].first - vec[p].first > mx && i != p){
                mx = vec[i].first - vec[p].first;
                ans = make_pair(vec[p].second,vec[i].second);
            }
            p = i + 1;
        }
    }
    cout << "! " << ans.first << ' ' << ans.second << endl;
}

额外思考

竞赛图缩点之后会变成一个类似链状物，缩点后的图上关于度有一些很神奇的性质。

日志

本页面创建于 2024/08/17 11:55

UPD-1：2024/09/04 20:25

更新了线性解法。