Starters183 P4 - Complete MST

#上界・下界 #二分探索 #グラフ

問題

\(N\) 頂点からなる完全グラフがある。辺の重みは0か1のいずれかである。辺は \(\frac{N(N-1)}{2}\) 本存在するが、そのうちのちょうど \(M\) 本の辺の重みが1であり、残りの辺の重みは0である。
さて、このグラフの最小全域木を構成することを考える。最小全域木の重みとしてあり得るもの集合を \(W\) とするとき、 \(\sum_{i\in W} i\) を求めよ。 Link

解法

まず、達成可能な重みの最小値・最大値を求める。

達成可能な最小値

便宜上、重みが0である辺の本数を \(K\) と置く。 \(K=\frac{N(N-1)}{2} - M\) である。
いま、 \(K\geq N-1\) であるならば、0が達成可能である。これは、最小全域木に含まれる辺の本数が \(N-1\) 本であり、うまく辺を配置することでその全てを重み0で構成することができることから言える。
\(K

達成可能な最大値

最大値を達成するためには、できるだけ重み1の辺を採用したい。が、MSTなので、「ある頂点から重み0の辺で繋がっている頂点が存在する場合」は重み0の辺を採用することになってしまう ので、「ある頂点から出る辺を全て重み1にする」という構築を行うことによって全体の重みを増やすことが可能である。2頂点が1つの辺を共有することに注意すると、重み \(x\) を達成するためには \(\sum_{i=1}^x N-i\) 本の辺が必要となる。 \(M\) 以下で最大の \(x\) が二分探索によって求まるので、これを最大値とすれば良い。

達成可能な最小値/最大値の間に含まれるものは全て達成可能 なので、あとは適当に合計を求めてあげれば良い。 提出

ll sum(ll n) {
    return n*(n+1)/2;
}

void solve() {
    ll n, m; cin >> n >> m;
    ll k = n*(n-1)/2 - m;

    ll upper;
    {
        ll ok = 0;
        ll ng = n;
        while(abs(ok-ng)>1) {
            ll mid = (ok+ng)/2;
            if(mid*n-sum(mid) <= m) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        upper = ok;
    }

    ll lower = ((k>=n-1)?0:n-1-k);
    lower--;

    cout << sum(upper) - sum(lower) << '\n';

}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t=1;
    cin >> t;
    while(t--)solve();
}