CF 350E Wrong Floyd

题目描述

https://codeforces.com/problemset/problem/350/E

Solution

注意到如果 $u$ 到 $v$ 的所有路径都满足路径有点不是 $floyd$ 中的关键点，那么 $u$ 到 $v$ 的最短路是错误的

所以我们考虑这样构图，拿出一个关键点，然后其他点随便连边，指定的这个关键点只与非关键点连边

这样最多能消耗 $\frac{n(n-1)}{2}-(k-1)$ 条边

#include <iostream>
#include <vector>
#define maxn 310
using namespace std;

int n, m, k, a[maxn], b[maxn];

bool vis[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> k;
    for (int i = 1; i <= k; ++i) cin >> a[i], vis[a[i]] = 1;
    for (int i = 1; i <= n; ++i) if (!vis[i]) b[++b[0]] = i; 
    if (n == k || m > n * (n - 1) / 2 - k + 1) return cout << "-1\n", 0; 
    vector<pair<int, int>> ans;
    for (int i = 1; i <= n - k; ++i) ans.emplace_back(a[1], b[i]);
    for (int i = 2; i <= k; ++i) ans.emplace_back(a[i], b[1]);
    for (int i = 2; i <= k; ++i)
        for (int j = 2; j <= n - k; ++j) ans.emplace_back(a[i], b[j]);
    for (int i = 1; i <= n - k; ++i)
        for (int j = i + 1; j <= n - k; ++j) ans.emplace_back(b[i], b[j]);
    for (int i = 2; i <= k; ++i)
        for (int j = i + 1; j <= k; ++j) ans.emplace_back(a[i], a[j]);
    for (int i = 0; i < m; ++i) cout << ans[i].first << " " << ans[i].second << "\n"; 
    return 0;
}