PKU 3631 Cuckoo Hashing
http://poj.org/problem?id=3631
m個の文字列(d1,d2,...,dm)をハッシュ関数h1,h2で0〜n-1の整数にした値h1(di),h2(di)が与えられる。
これを、要素数nのテーブルTに以下のように突っ込んでいく。
・T[h1(di)]が空ならそこに入れる。
・T[h1(di)]が空でなく、T[h2(di)]が空ならそこに入れる。
・どちらも空でないならdiをT[h1(di)]に入れて、もともと入っていたやつをT[h1(di)]に入れるときに使った関数とは別の関数を使って入れなおしていくというのを衝突がなくなるまで繰り返す。
二部グラフ最大マッチング。
全部マッチングできればOK。これって実際に使われているハッシング方法のひとつなんでしょうか?
cin使ったらTLEしました。
int match[10000]; int in[10000][2]; bool vis[10000]; bool augment(int v){ vis[v]=true; rep(i,2){ int to=in[v][i]; if(match[to]==-1 || !vis[match[to]] && augment(match[to])){ match[to]=v; return true; } } return false; } void solve(){ int m,n; scanf("%d%d",&m,&n); rep(i,m) scanf("%d%d",in[i],in[i]+1); memset(match,-1,sizeof(match)); rep(i,m){ memset(vis,0,sizeof(vis)); if(!augment(i)){ puts("rehash necessary"); return; } } puts("successful hashing"); } main(){ int t; scanf("%d",&t); while(t--) solve(); }