ARC093 E : Bichrome Spanning Tree(900)
作成日：2018.08.18
最終更新日：2018.08.18
問題概要
$N$個の頂点と頂点$U_i , V_i$を結び$W_i$の重みをもつ$M$本の辺からなる無向グラフがある。
このグラフの辺を白か黒に塗る方法で、2色両方を含む全域木のうち最も重みの総和が小さいもの(以下、白黒最小全域木と呼ぶ)のそれが$X$であるものの個数を$10^9 + 7$で割った余りを求めよ。
制約
$1 \leq N \leq 1000$
$1 \leq M \leq 2000$
$1 \leq U_i , V_i \leq N$
$1 \leq W_i \leq 10^9$
$1 \leq X \leq 10^{12}$
与えられるグラフは連結で単純
考え方
クラスカル法を元にして考える。
以下では、辺は重みの小さい順にソートされているものとする。
グラフが単純であるから、色の塗り方にかかわらず$1$番目の辺は必ず使われる。
そこで仮に$1$番目の辺を白で塗ることにする。
白黒最小全域木を考えるから、黒で塗る辺を1つ固定して白黒最小全域木に含まれるとすると良さそうである。
ただこれだけだと他の辺の塗り方を重複がないように考えるのは大変だから、固定した辺が[*]白黒最小全域木中の黒い辺のうち番号が最も小さくなるような塗り方に限定することにする。
固定した辺の番号を$k$($1$番目は白なので$k \geq 2$)とし、以下では$k$番目の辺が[*]を満たす塗り方を考える。
$k$番目以外の辺をすべて白で塗ったものは明らかに[*]を満たすから、辺を黒く塗れる条件を考えれば良い。
$k$未満の番号の辺を黒く塗ったらいけないのは、その辺を使うと白黒最小全域木の重みの総和が$k$番目の辺を使った時のそれ以下になる時である。
また$k$より大きい番号の辺を黒く塗ったらいけないのは、その辺を使うと白黒最小全域木の重みの総和が$k$番目の辺を使ったときのそれ未満になる時である。
以上より、$k$番目の辺を全域木に含めるとした時の重みの総和の最小値が分かれば答えを求められることが分かる。
これは$k$番目の辺を本来の順序を無視して選んだ後、クラスカル法を適用すれば求められる。
計算量はほぼ$O(M^2)$(Union-Findを使うため)であるから、十分高速である。
ソースコード
マクロ等はこちら
Union_Find
void uni(int a , int b)
頂点$a$を含む集合と頂点$b$を含む集合を併合する
bool find(int a , int b)
頂点$a$と頂点$b$が同じ集合であるかを判定する
int member(int a)
頂点$a$を含む集合の大きさを返す
const LL mod = 1e9 + 7;
int N,M;
LL X;
vector<tuple<LL,int,int>> V;
LL solve(int a){
Union_Find uf;
LL ret = get<0>(V[a]);
uf.uni(get<1>(V[a]),get<2>(V[a]));
repp(i,0,M) if(!uf.find(get<1>(V[i]),get<2>(V[i]))){
ret += get<0>(V[i]);
uf.uni(get<1>(V[i]),get<2>(V[i]));
}
return uf.member(1) == N ? ret : 1e16;
}
int main(){
cin >> N >> M >> X;
repp(i,0,M){
int a,b; LL c; cin >> a >> b >> c;
V.PB(make_tuple(c,a,b));
}
sort(V.begin(),V.end());
LL ans = 0;
LL z = 2;
repm(i,M-1,0){
LL w = solve(i);
if(w >= X){
if(w > X) (ans *= 2) %= mod;
else (ans += z) %= mod;
z = z * 2 % mod;
}
}
cout << ans << endl;
return 0;
}解法まとめ
辺は重みでソートしておく。(23行)
$1$番重みの小さい辺以外の辺それぞれにおいて、その辺を全域木に含めるとした時の重みの総和の最小値$w_i$を求める。(6-15行)
そして$w_i = X$であるような辺において、$w_j \gt X$$(j \lt i)$,$w_j \geq X$$(j \gt i)$となるような$j$の個数$n_i$を求め、$2^{n_i}$の総和の$2$倍が答えである。
但し上のコードでは、辺を重みの大きい順に見ていき、$w_i \gt X$なら答えを$2$倍、$w_i = X$なら答えに$2$の[今まで見てきた辺のうち$w_j \geq X$となる個数+1]乗($z$)を足すことでこれを求めている。(24-33行)