SRM 694 Div1 medium : DistinguishableSetDiv1
問題概要 :
n人にm回質問をする.
人と質問にはそれぞれ0からn-1,0からm-1まで番号が割り振られている.
人iの質問jに対する回答は英大文字('A'~'Z')として表現される.
各人の各質問への回答が入力として与えられる.
全ての人を区別するためにしなければならない質問の集合は何通りあるか.
解法 :
動的計画法
区別するためにしなければならない質問の集合を数え上げるのではなく、
区別できない質問の集合を数え上げる.
異なる2人を選び、その人らを区別できない最大の質問の集合を求める.
この集合は2人が同じ回答をした質問の集合である.
このような集合から1つ要素を取り除いた集合もまた区別できない質問の集合なので、
要素を取り除くことでそこから得られる区別できない質問の集合を全て列挙する.
あとはこれを全ての異なる2人に対して行えば良い.
本番は解けてないのでwriter解を見て解いた.
本番中は「Twenty Questionsっぽい問題だな〜」と考えていたけど、全く違った残念
コード :
bool dp[1<<20]; class DistinguishableSetDiv1 { public: int count(vector <string> answer) { int n = answer.size(); int m = answer[0].size(); rep(i,n) REP(j,i+1,n) { int state = 0; rep(k,m) if( answer[i][k] == answer[j][k] ) state |= (1<<k); dp[state] = true; } int cnt = 0; for(int state=((1<<m)-1);state>=0;--state) if( dp[state] ) { rep(i,m) if( (state>>i) & 1 ) dp[state&~(1<<i)] = true; } rep(i,(1<<m)) cnt += dp[i]; return (1<<m)-cnt; } };
SRM 694 Div1 easy : TrySail
問題概要 :
n人の生徒からなるクラスがある.
各生徒には強さがあり、それらは0以上255以下の整数として表される.
n人の生徒を3つのグループに分ける.
ただし、グループ分けを行う際に、だれも生徒が属さないようなグループが出来てはいけない.
グループの強さはそのグループに属する生徒の強さのbitwise xorをとった値とする.
このとき、3つのグループの強さの総和を最大化し、その値を返せ.
制約 :
3 <= n <= 50
0 <= 生徒の強さ <= 255
解法 :
制約を見てみると強さも生徒数も少ないので、そのまま配列を確保してDPする.
3つのグループには1から順に3まで番号が割り振られているものとする.
dp[i][j][k][l] := グループ3の最大値
i : 各グループに生徒を1人以上割り当てたかどうかをビットで表す ( 0 <= i < (1<<3) )
j : グループ1の現在の強さ ( 0 <= j < (1<<8) )
k : グループ2の現在の強さ ( 0 <= k < (1<<8) )
l : curとnext ( 0 <= l < 2 )
他の人のコードを見てみると2次元配列で解いていた人もいたでのメモリ節約できるらしい
コード :
#define MAX (1<<8) int dp[10][MAX][MAX][2]; class TrySail { public: int get(vector <int> vec) { memset(dp,-1,sizeof dp); int n = (int)vec.size(); dp[0][0][0][0] = 0; rep(i,n) { int cur = i & 1; int next = (i+1) & 1; { rep(j,(1<<3)) rep(k,MAX) rep(l,MAX) dp[j][k][l][next] = -1; } rep(bit,(1<<3)) { rep(p1,MAX) { rep(p2,MAX) { if( dp[bit][p1][p2][cur] == -1 ) continue; rep(sel,3) { int nbit = bit | (1<<sel); int np1 = p1; int np2 = p2; int np3 = dp[bit][p1][p2][cur]; if( sel == 0 ) np1 = np1 ^ vec[i]; if( sel == 1 ) np2 = np2 ^ vec[i]; if( sel == 2 ) np3 = np3 ^ vec[i]; dp[nbit][np1][np2][next] = max(dp[nbit][np1][np2][next], np3); } } } } } int maxi = 0; rep(j,MAX) rep(k,MAX) if( dp[(1<<3)-1][j][k][n&1] != -1 ) { maxi = max(maxi,dp[(1<<3)-1][j][k][n&1]+j+k); } return maxi; } };
AOJ 1314 : Matrix Calculator
問題概要 :
問題文で定義されている Matrix Calculator を実装せよ
シンタックスはBNFで与えられる
Matrix Calculator : 行列計算を行うプログラム
Matrix Calculator の機能等を適当に列挙
1. +, -, * : 行列の加算、減算、乗算
2. - : 単項演算子のマイナス
3. 行列の各要素の値は2^15(=32768)でmodをとった値であり、0以上32767以下 (負の場合は正になるまで2^15を加算し続ける)
4. 行列 * 定数 もしくは 定数 * 行列 の場合、行列内の各要素に定数を掛ける
5. 行列(1行k列の行列,1行l列の行列)はk行l列の行列を返す (行列の各要素v(i,j)は元の行列の要素w(k[i],l[j]) )
6. 行列' は転置行列
解法：
BNFに従って実装する
基本的にBNFが書いてあるときはそれに従って再帰下降型構文解析を行う
ただ、そのまま実装できない場合があるので注意
具体的には、
1. 左再帰が存在する
- 例 : program ::= assignment | program assignment
2. 何文字か先読みしないと曖昧な場合がある
- 例 : primary ::= inum | var | matrix | "(" expr ")" | indexed-primary | transposed-primary
indexed-primary ::= primary "(" expr "," expr ")"
"(" が来たときに "(" expr ")" なのか indexed-primary の "(" expr "," expr ")" なのか先読みしないとわからない
これらの対処は次の通り
1. 文法を等価で左再帰を持たない文法に変換する
- program ::= assignment | program assignment => program ::= assignment | assignment program
( その他についての具体的な変換方法は、残念ながら書けない ( 直感でやってしまった ( 左再帰 除去 あたりでぐぐるとでてくると思う それかコンパイラの本（ドラゴンブックとか を読むとあるはず
2. 先読みする
- "(" がきたら、それが"("...")"なのか"("...","...")"なのかを判定して場合分けする
- 括弧の対応関係をもとめる方法( int cnt=0 を "(" なら +1, ")" なら -1 )をやって cnt == 1 であれば今見ている括弧の直下にある要素なので、そこに","があるようであれば "("...","...")"
あとはバグにすぐ気付けるようにassertかけまくって(※重要)実装を頑張る
コード:
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;++i) #define rep(i,n) REP(i,0,n) using namespace std; typedef vector<int> VI; typedef vector<VI> VVI; typedef VVI matrix; ostream& operator << (ostream &os,const matrix &mat) { rep(i,(int)mat.size()) { rep(j,(int)mat[i].size()) { if( j ) os << " "; os << mat[i][j]; } if( i+1 != (int)mat.size() ) os << endl; } return os; } const int MOD = 32768; matrix identity(int n) { matrix A(n,vector<int>(n,0)); for(int i=0;i<n;i++) A[i][i] = 1; return A; } matrix multi(const matrix& A,const matrix& B){ if( (int)A.size() == 1 && (int)A[0].size() == 1 ) { matrix C(B.size(),VI(B[0].size())); int coef = A[0][0]; rep(i,(int)B.size()) { rep(j,(int)B[0].size()) { C[i][j] = B[i][j] * coef; C[i][j] %= MOD; } } return C; } if( (int)B.size() == 1 && (int)B[0].size() == 1 ) { matrix C(A.size(),VI(A[0].size())); int coef = B[0][0]; rep(i,(int)A.size()) { rep(j,(int)A[0].size()) { C[i][j] = A[i][j] * coef; C[i][j] %= MOD; } } return C; } matrix C(A.size(),vector<int>(B[0].size())); for(int i=0;i<C.size();++i) for(int j=0;j<C[i].size();++j) for(int k=0;k<A[i].size();++k) { C[i][j] += ( A[i][k] * B[k][j] ); while( C[i][j] < 0 ) C[i][j] += MOD; C[i][j] %= MOD; } return C; } matrix add(const matrix& A,const matrix& B){ assert( A.size() == B.size() ); matrix C(A.size(),vector<int>(A[0].size(),0)); rep(i,(int)A.size()) { assert( A[i].size() == B[i].size() ); rep(j,(int)A[0].size()) { C[i][j] = ( A[i][j] + B[i][j] ) % MOD; while( C[i][j] < 0 ) C[i][j] += MOD; C[i][j] %= MOD; } } return C; } matrix sub(const matrix& A,const matrix& B){ assert( A.size() == B.size() ); matrix C(A.size(),vector<int>(A[0].size(),0)); rep(i,(int)A.size()) { assert( A[i].size() == B[i].size() ); rep(j,(int)A[0].size()) { C[i][j] = ( A[i][j] - B[i][j] ) % MOD; while( C[i][j] < 0 ) C[i][j] += MOD; C[i][j] %= MOD; } } return C; } matrix neg(const matrix& A) { matrix B(A.size(),vector<int>(A[0].size(),0)); rep(i,(int)A.size()) { rep(j,(int)A[i].size()) { B[i][j] = -A[i][j]; while( B[i][j] < 0 ) B[i][j] += MOD; B[i][j] %= MOD; } } return B; } matrix transpose(const matrix& A) { matrix B(A[0].size(),vector<int>(A.size(),0)); rep(i,(int)A[0].size()) { rep(j,(int)A.size()) { B[i][j] = A[j][i]; } } return B; } matrix factor(); matrix term(); matrix expr(); matrix transposed_primary(matrix); matrix indexed_primary(matrix); matrix indexed_primary_and_transposed_primary(matrix); map<char,matrix> buffer; string context; int ptr; matrix row() { matrix p = expr(); while( ptr < (int)context.size() && context[ptr] == ' ' ) { ++ptr; matrix q = expr(); assert( p.size() == q.size() ); rep(i,(int)p.size()) { rep(j,(int)q[i].size()) { p[i].push_back(q[i][j]); } } } return p; } matrix row_seq() { matrix p = row(); while( ptr < (int)context.size() && context[ptr] == ';' ) { ++ptr; matrix q = row(); rep(i,(int)q.size()) p.push_back(q[i]); } return p; } matrix c_matrix() { assert( context[ptr] == '[' ); ++ptr; matrix p = row_seq(); assert( context[ptr] == ']' ); ++ptr; return p; } bool next_is_indexed_primary() { assert( ptr < (int)context.size() && context[ptr] == '(' ); int i=ptr+1,cnt = 1; for(;i<(int)context.size();++i){ if( context[i] == '(' ) ++cnt; else if( context[i] == ')' ) --cnt; if( cnt == 0 ) { ++i; break; } } if( context[i] != '(' ) return false; ++i,cnt = 1; for(;i<(int)context.size();++i) { if( context[i] == '(' ) ++cnt; else if( context[i] == ')' ) --cnt; if( cnt == 0 ) break; if( cnt == 1 && context[i] == ',' ) return true; } return false; } bool next_is_indexed_primary2() { int i=ptr+1,cnt = 1; while( i < (int)context.size() && context[i] != '(' ) ++i; if( i >= (int)context.size() ) return false; assert( context[i] == '(' ); ++i,cnt = 1; for(;i<(int)context.size();++i) { if( context[i] == '(' ) ++cnt; else if( context[i] == ')' ) --cnt; if( cnt == 0 ) break; if( cnt == 1 && context[i] == ',' ) return true; } return false; } bool is_indexed_primary() { assert( ptr < (int)context.size() && context[ptr] == '(' ); int i=ptr+1,cnt = 1; for(;i<(int)context.size();++i) { if( context[i] == '(' ) ++cnt; else if( context[i] == ')' ) --cnt; if( cnt == 0 ) break; if( cnt == 1 && context[i] == ',' ) return true; } return false; } matrix primary() { if( context[ptr] == '(' && !next_is_indexed_primary() ) { ++ptr; matrix p = expr(); assert( ptr < (int)context.size() ); assert( context[ptr] == ')' ); ++ptr; return indexed_primary_and_transposed_primary(p); } else if( context[ptr] == '(' ) { ++ptr; matrix p = expr(); assert( context[ptr] == ')' ); ++ptr; return indexed_primary_and_transposed_primary(indexed_primary(p)); } if( context[ptr] == '[' ) { return indexed_primary_and_transposed_primary(c_matrix()); } if( 'A' <= context[ptr] && context[ptr] <= 'Z' ) { char var = context[ptr++]; assert( buffer.count(var) ); return indexed_primary_and_transposed_primary(buffer[var]); } if( '0' <= context[ptr] && context[ptr] <= '9' ) { int v = 0; while( ptr < (int)context.size() && '0' <= context[ptr] && context[ptr] <= '9' ) { v *= 10; v += ( context[ptr++] - '0' ); } return indexed_primary_and_transposed_primary(matrix(1,vector<int>(1,v))); } assert(false); } matrix indexed_primary_and_transposed_primary(matrix p) { while( ptr < (int)context.size() && ( context[ptr] == '\'' || ( context[ptr] == '(' && is_indexed_primary() ) ) ) { char opr = context[ptr]; if( opr == '\'' ) { p = transposed_primary(p); } else { p = indexed_primary(p); } } return p; } matrix indexed_primary(matrix p) { if( ptr < (int)context.size() && context[ptr] == '(' ) { if( is_indexed_primary() ) { ++ptr; matrix k = expr(); assert( ptr < (int)context.size() && context[ptr] == ',' ); ++ptr; matrix l = expr(); assert( ptr < (int)context.size() && context[ptr] == ')' ); ++ptr; assert( (int)k.size() == 1 ); assert( (int)l.size() == 1 ); matrix np = matrix((int)k[0].size(),VI((int)l[0].size())); rep(i,(int)k[0].size()) { int y = k[0][i]-1; rep(j,(int)l[0].size()) { int x = l[0][j]-1; np[i][j] = p[y][x]; } } p = np; } } return p; } matrix transposed_primary(matrix p) { if( ptr < (int)context.size() && context[ptr] == '\'' ) { int cnt = 0; while( ptr < (int)context.size() && context[ptr] == '\'' ) { ++ptr, ++cnt; } if( cnt & 1 ) { p = transpose(p); } } return p; } matrix factor() { assert( ptr < (int)context.size() ); if( context[ptr] == '-' ) { int cnt = 0; while( context[ptr] == '-' ) { ++cnt, ++ptr; } matrix p = factor(); if( cnt & 1 ) { p = neg(p); } return p; } return primary(); } matrix term() { matrix p = factor(); while( ptr < (int)context.size() && context[ptr] == '*' ) { ++ptr; matrix q = factor(); p = multi(p,q); } return p; } matrix expr(){ matrix p = term(); while( ptr < (int)context.size() && ( context[ptr] == '+' || context[ptr] == '-' ) ) { char opr = context[ptr++]; matrix q = term(); if( opr == '+' ) { p = add(p,q); } else if( opr == '-' ) { p = sub(p,q); } } return p; } void assignment() { assert( 0 <= ptr && ptr < (int)context.size() ); char var = context[ptr++]; assert( 0 <= ptr && ptr < (int)context.size() ); assert( context[ptr] == '=' ); ++ptr; matrix mat = expr(); assert( 0 <= ptr && ptr < (int)context.size() ); assert( context[ptr] == '.' ); ++ptr; buffer[var] = mat; cout << mat << endl; } void exec() { ptr = 0; assignment(); } int main() { int n; while( cin >> n, n ) { cin.ignore(); buffer.clear(); rep(_,n) { getline(cin,context); exec(); } puts("-----"); } return 0; }
Graphviz でノード名にプライムをつけたかった
Graphvizでノード名にプライムをつけようとしたらエラーが出た
ググっても解決策がでてこなかったのでメモ
解決策 : ノード名を"で囲む
ダメな例 :
digraph g {
node0' [color="#ffffff", fontcolor="#ffffff"];
node1', node2->;
}
良い例 :
digraph g {
"node0'" [color="#ffffff", fontcolor="#ffffff"];
"node1'", "node2->";
}
SRM Div1 easy : BiconnectedDiv1
問題概要 :
n個のノードが存在し、それらは0からn-1まで番号が割り振られている
ノードiはi+1がn-1以下であればノードi+1に向けて重みw1[i]の辺を持つ
また、ノードiはi+2がn-1以下であればノードi+2に向けて重みw2[i]の辺を持つ
各辺は無向辺である
このようにして構成されるグラフから何本か辺を削除する
ただし、辺を削除した後はそのグラフの任意の異なる２頂点u,v間にパスが存在する必要がある
（つまり、uからvに残っている辺をたどって移動できる必要がある)
上の制約を満たした上で0本以上辺を削除したとき、残った辺の重みの総和の最小値を求めよ
解法 :
動的計画法で解いた
まず、辺を消した後に条件を満たすようなグラフがどのようなものなのかを考える
これは全てのノードが１つの閉路に含まれるグラフである
このようなグラフであれば、どこを消しても少なくとも１本はパスが存在する
全てのノードが１つの閉路に属していない場合、閉路に属していないノードから出ている辺を削除すると連結でなくなる
グラフ全体が１つの閉路になるための条件は各ノードの次数が2以上で連結であることである
（グラフが閉路かどうかの判定は各ノードの次数が偶数で連結であること 今回は閉路+αがあっても良いので2以上にした）
あとは各ノードの次数が2未満にならないように辺を削除するかしないかでDPをする
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; typedef long long ll; const int IINF = INT_MAX; struct Edge { int dst,w; }; #define MAX 300 vector<Edge> G[MAX]; int dp[MAX]; class BiconnectedDiv1 { public: int V; int minimize( vector <int> w1, vector <int> w2 ) { V = (int)w1.size() + 1; rep(i,MAX) G[i].clear(); memset(dp,0,sizeof dp); int sum = 0; rep(i,(int)w1.size()) { G[i].push_back((Edge){i+1,w1[i]}); G[i+1].push_back((Edge){i,w1[i]}); sum += w1[i]; } rep(i,(int)w2.size()) { G[i].push_back((Edge){i+2,w2[i]}); G[i+2].push_back((Edge){i,w2[i]}); sum += w2[i]; } int maxi = 0; REP(v,1,V-1) { dp[v] = max(dp[v],dp[v-1]); if( (int)G[v].size() >= 3 ) { rep(i,(int)G[v].size()) { Edge &e = G[v][i]; if( v > e.dst ) continue; if( (int)G[e.dst].size() < 3 ) continue; dp[e.dst] = max(dp[e.dst],dp[v]+e.w); maxi = max(maxi,dp[e.dst]); } } } return sum - maxi; } };
ACM-ICPC 2016 国内予選 参加記
最後の国内予選なので参加記を残そうかと
チームは私と後輩Sと後輩Tです。（イニシャルだけだと去年と同じだけど後輩Tは去年とは別の人
[追記]後輩Tではなく後輩Mでした、後輩Mさんごめんなさい
リハーサル
後輩Sは2,3限に授業があるため不参加
後輩Mとともに会場準備とプリンタの設定を行う
お菓子とMAXコーヒーとレッドブルとT島屋で買った100g1670円のブルーマウンテンを挽いていれたコーヒーを飲む
自己紹介を書いたりする
TwitterのTLを眺めながら後輩らの精神状況が不安定であることを確認する
コンテスト中のチームの動きを確認する
コンテスト開始を待つ
コンテスト
A問題
ソートするだけっぽい
絶対AでWAを出したくないので後輩Sに「本当にそれだけ？」とn回確認した
「条件どうこういってたけど、それはなんだったの？」「本当にそれだけ？？」「えっ」
コードを書く、サンプルは通る
まぁ投げてみる => AC
良い感じ
１完
B問題
後輩Mから概要を聞く
全探索で良いみたい
書く=>サンプルが合わない
バグとりを二人でする
入力に現れる立候補者の他に１名立候補者を入れる必要があることが発覚
入れる、それに合わせてループを修正
サンプルは通る
まぁ投げてみる => AC
ちょっとつまったけど良い感じ
２完
C問題
後輩Sから概要を聞く
「エラトステネスの篩です、以上」
この説明から概要がつかめなかったで問題文に目を通す
なるほど、エラトステネスの篩っぽいものを書けば良いようだ
書く=>無限ループ
悲しい気持ちになりつつもデバッグ
無限ループは止まった
でもサンプルは合わない
後輩Sと色々話しながらバグを探す、修正
サンプルは通る
まぁ投げてみる => AC
プログラムを実行してからアウトプットが終わるまで２、３分かかっていて辛い感じだったけどまぁ通ったし良い感じ
３完
D問題
概要を聞く前に解けそうか聞いてみる
二人から分からないと返事が返ってきて悲しい気持ちになる
概要を聞く
「あれ、超見たことあるこれ絶対区間DPだゾ（適当」
という発言したはいいもののはっきりとした方針が浮かんでこない
とりあえず後ろの問題に一通り目を通す
Fぱっとみ簡単そう、でもさすがにDのほうが楽そう
Dをやることにする
冷静に考えて、bool memo[L][R]みたいな感じで全て消すことのできる区間を列挙してあとは
dp[i]:=iまでで作れる最大値 みたいなDPすれば良い
書く=>めっちゃバグる＝＞辛い気持ちになりつつ後輩Mと共にデバッグをする
暗黒時代の幕開け
後輩Mが正しい方針を示すもそれとは全く違う実装をして時間を無駄にする
頑張る
暗黒時代が終わる
サンプルは通る
まぁ投げてみる => AC
スコアボードを確認するとまぁ良いでしょみたいな順位にいたので良い感じ
４完
とりあえず残りの問題のどれに挑戦するか話し合う
E ... 一番ダメそう
F ... 一番いけそう
G ... 自分には無理そう、後輩Sは挑戦したいらしい
H ... 二番目にいけそう
というわけで自分はFを書き、
後輩SはGを考え、
後輩MはHを考えることに
F問題
内包関係をグラフにするとそれは木になるし、だったらあとは木の同型判定でしょ
まだ１時間以上あるしいける木がする
実装開始と共に暗黒時代が幕を開ける
残り１時間 => まだまだ書くことがある
残り30分 => まだまだまだ書くことがある
残り10分 => まだまだまだまだ書くことがある、なんだこれは
コンテストが終わった
実装力が足りていない（もしくはコーダーが足りていない
感想
アジアに向けてコーダーを育てようと決意
SRM 692 Div1 easy : HardProof
問題概要 :
任意の２点間に辺があるような重み付き有向グラフが隣接行列Dとして与えられる
このグラフはn個の頂点から成り、各頂点には0から順にn-1まで番号が割り振られている
全ての頂点を少なくとも１回以上訪れるような閉路について考えたとき、
この閉路に含まれる辺の重みの最大値と最小値の差の最小値を求めよ
解法 :
強連結成分分解 + 二分探索で解いた
まず、閉路中に存在する辺の重みの最大値と最小値を決める
ただし愚直に最大値と最小値を決めてしまうと全ての辺の重みが異なる場合にTLEする
( 最大値、最小値の取りうる数はそれぞれ2500なので総当たりすると2500 * 2500, その後の処理に2500かかるので 2500^3 で TLE する その後の処理をlogくらいに抑えれればTLEしないけど)
そこで、最小値だけを総当たりで決める
最小値が決まったとき、最小値以上の最大値の最小値は二分探索により求めることができる
このとき、与えられたグラフの中から辺の重みが最小値未満もしくは最大値より大きいものを除いたグラフについて考える
このグラフ中に、全ての頂点を少なくとも１回以上訪れるような閉路が存在すれば良い
ここでは既に余計な辺を削除してあるので、このグラフ中に平路が存在するかどうかを判定すれば良い
これはグラフ中に橋が存在するかどうかで判断できる
( 橋とは？ 参考 : http://hos.ac/slides/20110504_graph.pdf
橋 : グラフ中に存在する辺のうち、それを取るとグラフの連結成分数が増えるようなもののこと)
今回グラフは有向グラフなので、強連結成分の数が１つかどうかで判断できる
強連結成分の数が２以上なら、異なる２つの強連結成分同士を結ぶような辺が橋になるからである
V,Eをそれぞれグラフの頂点集合、辺集合とすると計算量は
閉路中の辺の重みの最小値を総当たりするので |V| = 2500
二分探索で最大値を決定するので log2(|V|) = log2(2500) ≒11.287712379549449
強連結成分分解 |V| + |E| = 50 + 2500
O( |V| * log(|V|) * (|V|+|E|) )
最悪ケースでは 2500 * log2(2500) * 2550 ≒ 70548202.37218405となる
10^8以下なので十分１秒以内に終わる
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) #define EPS 1e-10 #define equals(a,b) (fabs((a)-(b)) < EPS) using namespace std; const int IINF = INT_MAX; int V; int mat[51][51]; bool visited[51]; class HardProof { public: int lower, upper; vector<vector<int> > G,rG; vector<bool> used; vector<int> cmp,vs; void add_edge(int s,int t){ G[s].push_back(t); rG[t].push_back(s); } void dfs(int v){ used[v] = true; for(int i=0;i<(int)G[v].size();i++) if( !used[G[v][i]] ) dfs(G[v][i]); vs.push_back(v); } void rdfs(int v,int k){ used[v] = true; cmp[v] = k; for(int i=0;i<(int)rG[v].size();i++) if( !used[rG[v][i]] ) rdfs(rG[v][i],k); } int scc(){ rep(i,V) used[i] = false; vs.clear(); rep(v,V) if( !used[v] ) dfs(v); rep(i,V) used[i] = false; int k = 0; for(int i=vs.size()-1;i>=0;i--) if( !used[vs[i]] ) rdfs(vs[i],k++); return k; } bool check() { if( lower > upper ) return false; G.clear(), rG.clear(), cmp.clear(), used.clear(); G.resize(V,vector<int>()), rG.resize(V,vector<int>()),cmp.resize(V), used.resize(V); rep(i,V) { rep(j,V) if( i != j && ( lower <= mat[i][j] && mat[i][j] <= upper ) ) { add_edge(i,j); } } return scc() == 1; } int minimumCost(vector <int> D) { V = sqrt((int)D.size()); if( V == 1 ) return 0; rep(i,V) rep(j,V) mat[i][j] = D[i*V+j]; vector<int> lowers; rep(i,V) rep(j,V) lowers.push_back(mat[i][j]); sort(lowers.begin(),lowers.end()); lowers.erase(unique(lowers.begin(),lowers.end()),lowers.end()); int mini = IINF; rep(i,(int)lowers.size()) { lower = lowers[i]; int L = 0, R = ((int)lowers.size()); while( L + 1 < R ) { int M = ( L + R ) / 2; upper = lowers[M]; if( check() ) { R = M; mini = min(mini,upper-lower); } else { L = M; } } } return mini; } };
