| 
辺を追加削除するコストが与えられた時、無向グラフを最小コストで木にする問題。
辺の変更コストの小さい順に、重複した（消しても到達性が変わらない）辺を消していく。
その後同じくコストの小さい順に連結に寄与する辺を追加していく。
warshall-floyd でごりごり。冗長なコードになった。
自分への辺を追加していなかったり、隣接行列上で (i, j) を繋いだら (j, i) も繋がないといけないのを忘れていたりしてしばらく苦戦していたが、
ようやく終了 10 秒くらい前に手元のテストが通ったのでアプレットでコンパイルしたところで 糸冬 了 。
↓あとで (practice system test pass)
int dec(char c) { if('A'<=c&&c<='Z') return c-'A'; if('a'<=c&&c<='z') return c-'a'+26; return -1; } class KingdomReorganization { public: int getCost(vector <string> ki, vector <string> build, vector <string> destroy) { int N=ki.size(); vector<pair<int, pair<int, int> > > bu(N*N); vector<pair<int, pair<int, int> > > de(N*N); //VVI bu(N, VI(N, 0)); //VVI de(N, VI(N, 0)); REP(i, N) REP(j, N) bu[i*N+j] = MP(dec(build[i][j]), MP(i, j)); REP(i, N) REP(j, N) de[i*N+j] = MP(dec(destroy[i][j]), MP(i, j)); sort(ALL(de)); sort(ALL(bu)); cout<<bu<<endl; cout<<de<<endl; VVI orig(N, VI(N, 0)); REP(x, N) REP(y, N) if(ki[x][y]=='1') orig[x][y]=1; REP(x, N) orig[x][x]=1; int ans = 0; { VVI orig_r(N, VI(N, 0)); REP(x, N) REP(y, N) orig_r[x][y] = orig[x][y]; REP(k, N) REP(i, N) REP(j, N) orig_r[i][j] |= orig_r[i][k]&orig_r[k][j]; REP(ii, N*N) { int ei = de[ii].second.first; int ej = de[ii].second.second; int co = de[ii].first; VVI w(N, VI(N, 0)); REP(x, N) REP(y, N) w[x][y]=orig[x][y]; if(w[ei][ej]==0) continue; w[ei][ej] = w[ej][ei] = 0; REP(k, N) REP(i, N) REP(j, N) w[i][j] |= w[i][k]&w[k][j]; int ok=1; REP(i, N) REP(j, N) if(orig_r[i][j]==1 && w[i][j]==0) ok=0; if(ok) { ans+=co; orig[ei][ej] = orig[ej][ei] = 0; } } } { VVI orig_r(N, VI(N, 0)); REP(x, N) REP(y, N) orig_r[x][y] = orig[x][y]; REP(k, N) REP(i, N) REP(j, N) orig_r[i][j] |= orig_r[i][k]&orig_r[k][j]; cout<<orig_r<<endl; REP(ii, N*N) { int ei = bu[ii].second.first; int ej = bu[ii].second.second; int co = bu[ii].first; VVI w(N, VI(N, 0)); REP(x, N) REP(y, N) w[x][y]=orig[x][y]; if(w[ei][ej]==1 || w[ej][ei]==1) continue; w[ei][ej] = w[ej][ei] = 1; REP(k, N) REP(i, N) REP(j, N) w[i][j] |= w[i][k]&w[k][j]; cout<<w<<endl; int ok=0; REP(i, N) REP(j, N) if(orig_r[i][j]==0 && w[i][j]==1) ok=1; if(ok) { cout<<ei<<" "<<ej<<endl; ans+=co; orig[ei][ej] = 1; orig[ej][ei] = 1; REP(x, N) REP(y, N) orig_r[x][y] = orig[x][y]; REP(k, N) REP(i, N) REP(j, N) orig_r[i][j] |= orig_r[i][k]&orig_r[k][j]; cout<<"orig_r " <<orig_r<<endl; } } } return ans; } };
さらに後から、一旦すべて消して最小全域木に帰着させたやつを書いた。
最初に全部消すコストを数えておいて、辺の重みとして
を持つグラフの最小全域木を union-find を使った Kruskal で求める。
union-find は spaghetti source さんから。
int dec(char c) { if('A'<=c&&c<='Z') return c-'A'; if('a'<=c&&c<='z') return c-'a'+26; return -1; } struct UnionFind { vector<int> data; UnionFind(int size) : data(size, -1) { } bool unionSet(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool findSet(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } }; class KingdomReorganization { public: int getCost(vector <string> ki, vector <string> build, vector <string> destroy) { int ans = 0; int N=ki.size(); vector<pair<int, pair<int, int> > > bu; REP(i, N) REP(j, N) { if(ki[i][j]=='1') { bu.PB(MP(-dec(destroy[i][j]), MP(i, j))); ans += dec(destroy[i][j]); ki[i][j]=ki[j][i]='0'; } else { bu.PB(MP(dec(build[i][j]), MP(i, j))); } } sort(ALL(bu)); //cout<<bu<<endl; UnionFind uf(N); REP(ii, bu.size()) { int ei = bu[ii].second.first; int ej = bu[ii].second.second; int cost = bu[ii].first; if(uf.unionSet(ei, ej)) ans += cost; } return ans; } };
