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<N-1$の場合は重みが$N-K-1$となって、これは先程と同様に構築をするが、重み0の辺では充足しきれない分を重み1の辺で補う必要があるからである。

達成可能な最大値

最大値を達成するためには、できるだけ重み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) << '
';

}

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