[Medium] CF1054G New Road Network

简要题意

给定 $n$ 个点和 $m$ 个点集 $S_i$。构造一棵树使得每个点集在树上均构成一个连通块，或报告无解。

$T$ 组数据。$1\leq \sum n,\sum m,T\leq 2\times 10^3$。

思路

咋就 *3300 了啊……

不妨考虑构造的过程，当我们选择连接边 $(u,v)$ 时，若 $\exists S_i, \{u,v\}\subseteq S_i$，则我们称连接这条边助力限制 $S_i$ 的达成。那么若集合 $S_i$ 的限制最终满足，需要恰好 $|S_i|-1$ 次助力（经典结论：对于一个点数为 $n$ 的森林，其退化为一棵树当且仅当边数恰好为 $n-1$）。

于是可以建一个完全图，边 $(u,v)$ 的权为连接这条边可以助力多少个集合。利用 std::bitset 很容易 $O(\frac{n^3}{\omega})$ 求出所有边权。那么我们需要寻找一个生成树，满足所有集合都被助力了对应的次数。

由于生成树是没有环的，所以任意集合 $S_i$ 的导出子图一定是森林，故边数（助力次数） $\leq |S_i|-1$ 即需要达到上界。要求每一个集合的助力次数都达成上界，等价于让总和达到上界，因此只需要找到完全图的一个最大生成树（使用 Kruskal 或 Prim 均可，不是瓶颈），验证是否达到了上界即可。

时间复杂度 $O(\frac{n^3}{\omega})$。

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;

const int N = 2005;
int n, m, fa[N], cnt[N], req[N];
bitset<N> S[N];

struct edge {
    int u, v, w;
    bool operator>(const edge& rhs) const { return w > rhs.w; }
} g[N * N];

int find(int x){ return x == fa[x] ? x : fa[x] = find(fa[x]); }

void solve(){
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        string s; cin >> s, req[i] = count(s.begin(), s.end(), '1');
        for(int j=1;j<=n;j++) S[j][i] = s[j - 1] == '1';
    }
    int tot = 0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++) g[++tot] = {i, j, (int)((S[i] & S[j]).count())};
    }
    sort(g + 1, g + tot + 1, greater<edge>());
    iota(fa + 1, fa + n + 1, 1);
    vector<pair<int,int>> vp;
    for(int i=1;i<=tot;i++){
        int u = g[i].u, v = g[i].v, fu = find(u), fv = find(v);
        if(fu == fv) continue;
        fa[fu] = fv, vp.emplace_back(u, v);
        for(int j=1;j<=m;j++){
            if(S[u][j] && S[v][j]) cnt[j]++;
        }
    }
    for(int i=1;i<=m;i++){
        if(req[i] - 1 != cnt[i]) return cout << "NO" << '\n', void();
    }
    cout << "YES" << '\n';
    for(auto [u, v] : vp) cout << u << ' ' << v << '\n';
}

void clear(){
    fill(cnt + 1, cnt + m + 1, 0);
    for(int i=1;i<=n;i++) S[i].reset();
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t; cin >> t;
    while(t--) solve(), clear();
    return 0;
}

// Written by xiezheyuan

Submission