#include #include #include #include #include #include #include #include using namespace std; //-------------------------------------------------------------------- // 二部グラフ // {i:0..N-1} ←→ {j:0..N-1} // G[i] := the set of js connected to i // の最大マッチングを計算 //-------------------------------------------------------------------- void bipartite_maxmatch( vector< vector >& G, map& m_L2R, map& m_R2L ) { m_L2R.clear(); m_R2L.clear(); ExtendMatching: for(int i=0; i!=G.size(); ++i) { // 現在のマッチングに入っていない点iについて… if( m_L2R.count(i) ) continue; // iを始点とする増加路を探す map prev_L2R; map prev_R2L; // 幅優先で queue Q; Q.push(i); while( !Q.empty() ) { int t = Q.front(); Q.pop(); vector& es = G[t]; for(int k=0; k!=es.size(); ++k) { int j = es[k]; if( prev_R2L.count(j) ) continue; // 探索済み prev_R2L[j] = t; if( !m_R2L.count(j) ) // 現在のマッチングに入ってない場合 { // 増加路発見。マッチングを更新 for(int jj=j,ii=t;;) { m_L2R[ii] = jj; m_R2L[jj] = ii; if( !prev_L2R.count(ii) ) break; jj = prev_L2R[ii]; m_R2L.erase(jj); ii = prev_R2L[jj]; } goto ExtendMatching; // 次の増加路を探す } else // 現在のマッチングに入ってる場合 { int n = m_R2L[j]; prev_L2R[n] = j; Q.push(n); } } } } } //-------------------------------------------------------------------- // 二部グラフ // {i:0..N-1} ←→ {j:0..N-1} // G[i] := the set of js connected to i // の最小点被覆を計算。最大マッチングを与えること。 //-------------------------------------------------------------------- void bipartite_maxcover( vector< vector >& G, map& m_L2R, map& m_R2L, set& L, set& R ) { // 右 : 不飽和な頂点から交替路でいけるの全部 R.clear(); for(int i=0; i!=G.size(); ++i) if( !m_L2R.count(i) ) { queue Q; Q.push(i); while( !Q.empty() ) { int t=Q.front(); Q.pop(); for(int k=0; k!=G[t].size(); ++k) { int j = G[t][k]; if( !R.count(j) ) { R.insert(j); if( m_R2L.count(j) ) Q.push(m_R2L[j]); } } } } // 左 : 残り L.clear(); for(int j=0; j!=G.size(); ++j) if( m_R2L.count(j) && !R.count(j) ) L.insert( m_R2L[j] ); } //-------------------------------------------------------------------- // 重みつき二部グラフ // {i:0,…,N-1} ←[w[i][j]]→ {j:0,…,N-1} // の最大重み完全マッチを r[i] = j の形で求める。 // 最小重み点カバー問題との双対性を利用。Hungarian Method。 // 参考文献: http://www.cs.duke.edu/~schak/hungarian_matching.pdf //-------------------------------------------------------------------- void solve( vector< vector > w, vector& r ) { const int N = w.size(); // 重みつき点カバー:初期値 vector u(N), v(N); for(int i=0; i!=N; ++i) u[i] = *max_element( w[i].begin(), w[i].end() ); for(int j=0; j!=N; ++j) v[j] = 0; for(;;) { // Equality Subgraph Guvの構築 vector< vector > Guv(N); for(int i=0; i!=N; ++i) for(int j=0; j!=N; ++j) if( u[i]+v[j]-w[i][j] < 0.0000000001 ) //u+v==w Guv[i].push_back(j); // G_uv の最大マッチング M を計算 map m_L2R; map m_R2L; bipartite_maxmatch( Guv, m_L2R, m_R2L ); if( m_L2R.size() == N ) { // Found!! r.resize(N); for(map::iterator it=m_L2R.begin(); it!=m_L2R.end(); ++it) r[it->first] = it->second; return; } else { // G_uv の最小点被覆 L, R を計算 set L, R; bipartite_maxcover( Guv, m_L2R, m_R2L, L, R ); // Update幅を計算 double e = DBL_MAX; for(int i=0; i!=N; ++i) if( !L.count(i) ) for(int j=0; j!=N; ++j) if( !R.count(j) ) e = (e < u[i]+v[j]-w[i][j] ? e : u[i]+v[j]-w[i][j]); // Update!! for(int i=0; i!=N; ++i) if( !L.count(i) ) u[i] -= e; for(int j=0; j!=N; ++j) if( R.count(j) ) v[j] += e; } } } int main() { for(int nCase=0,N; cin>>N,N; ) { assert( 1<=N && N<=100 ); // 読み込み vector< vector > q(N, vector(N)); for(int i=0; i!=N; ++i) for(int j=0; j!=N; ++j) { double p; cin>>p; // 鍵穴iに鍵jを指したとき爆発する確率 assert( 0.00001<=p & p<=0.99999 ); q[i][j] = log(1-p) - log(0.0001); // 非負になるようにshift } // 重みを q[i][j] とした二部グラフの最大重み完全マッチを計算 // Σq_ijが最大 == logΠ(1-p_ij)が最大 // == Π(1-p_ij) が最大 // == 爆発しない確率が最大 vector answer(N); solve( q, answer ); // 出力 if(nCase++) cout << endl; for(int i=0; i!=N; ++i) cout << answer[i]+1 << endl; } }