CODE FESTIVAL 2016 Final G - Zigzag MST
問題
G: Zigzag MST - CODE FESTIVAL 2016 Final (Parallel) | AtCoder
問題概要
頂点が個のグラフがあり、からまで番号が順に付けられている。初期状態で辺は無く、以下のような辺追加クエリが個来る。
頂点番号とと重みが与えられて、
- とに重みの辺を張る。
- のindexを1つ進めて、とに重みの辺を張る。
- のindexを1つ進めて、とに重みの辺を張る。
- のindexを1つ進めて、とに重みの辺を張る。
- のindexを1つ進めて、とに重みの辺を張る。
という操作を以下同様に無限回繰り返す(ただし、このindexをすすめる時はmod N上で行う)。
このクエリが全て来た後の最小全域木に含まれる辺の重みの総和を答えよ。
アイデア
当日の会場の解説スタジオで聞いて、すごく綺麗な解答で口頭でしゃべっていたことも合わせて聞くととても自然に納得し理解できたので忘れないうちにまとめておこうと思った。
問題文上では無限回繰り返されることになっているが、一周以上しても多重辺になるだけで、コストは単調増加していくのでMSTを構成するにあたっては小さい方が残っていれば良い。
さて、1周分を考えてみると1つのクエリは次のような辺を張っていることになる↓
このクエリが全て読み込まれて、MSTを構成していこうという状況を考えるときに、クラスカル法でMSTを構成していくことを考えると、との間にある重みの辺がMSTとして入るかどうかはとが連結されているかどうかに依存していることになるわけだが、そのに注目するとはと重みの辺で繋がっている。つまり、このの辺を考慮する前の段階ですでにこの辺を使うかどうかが考慮されているわけで、使うか否かに関わらず、このの辺をMSTの辺として採用するのかを判定する段階において、必ずとは連結になっているわけなので、との間に張られた辺をtex:A+1]との間に張り直しても状況は変化しない。そして、張り替えると次のようになる↓
そうすると、同じ理由によっての辺がとの間の辺とすることが出来る↓
以下同様に、この操作を繰り返していくと次のようにとの間に重みの辺があり、そのほかは頂点番号が隣接しているところに等差が2で辺が張られていくというようなクエリに変換されることになる↓
そうすると、個のクエリを受けると、最終的にはそれぞれのクエリの始点との間に張られる重みの辺が個と、個の頂点の隣接しているところを結ぶ個の辺の合計個の辺でこのグラフが構成されることになり、この辺の個数ならクラスカル法によってMSTを求めることが可能である。
最後に、この輪のように構成される個の辺について、重になっているわけだがその中で最小のものを残すようにしたい。それは、重みが等差であることを利用して次のようにDPで求めることが出来る。
dp[i] = 頂点iと頂点(i+1)を繋ぐ辺の重みの最小値
として、全てを十分大きい値で初期化し、その次にdp[A]
を、dp[B]
をと最小値更新をかけていく。
そして、等差であることを利用すればdp[i] = min(dp[i], dp[i-1]+2)
という更新を2周すればこの輪について重みが最小の辺を構成することがで出来る。
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second struct UF{ int n; //正だったらその頂点の親,負だったら根で連結成分の個数 vector<int> d; UF() {} UF(int N):n(N), d(N,-1){} int root(int v){ if(d[v]<0) return v; return d[v]=root(d[v]); } bool unite(int X,int Y){ X=root(X); Y=root(Y); if(X==Y) return false; if(size(X) < size(Y)) swap(X,Y); d[X]+=d[Y]; d[Y]=X; return true; } int size(int v){ return -d[root(v)]; } bool same(int X,int Y){ return root(X)==root(Y); } }; const int N=200000; const ll INF=123456789012345LL; ll dp[N]; typedef pair<int,int> pi; typedef pair<ll,pi> edge; vector<edge> e; int main() { int n,Q; scanf(" %d %d", &n, &Q); fill(dp,dp+N,INF); while(Q--) { int a,b; ll c; scanf(" %d %d %lld", &a, &b, &c); e.pb(edge(c,pi(a,b))); dp[a]=min(dp[a],c+1); dp[b]=min(dp[b],c+2); } rep(_,2)rep(i,n) dp[i]=min(dp[i], dp[(i-1+n)%n]+2); rep(i,n) e.pb(edge(dp[i],pi(i,(i+1)%n))); sort(all(e)); UF uf(n); ll ans=0; rep(i,e.size()) { int a=e[i].se.fi, b=e[i].se.se; if(!uf.same(a,b)) { uf.unite(a,b); ans+=e[i].fi; } } printf("%lld\n", ans); return 0; }