面白い問題だった。
http://codeforces.com/contest/512/problem/C
問題
N匹のキツネがおり、各年齢はA[i]である。
これらのキツネを幾つかの円形のテーブルに分かれて着席させたい。
テーブルの数は任意だが、以下の2条件を満たさなければならない。
- 各テーブルに座るキツネは3匹以上
- テーブルで隣接するキツネの年齢の和は素数でなければならない
条件を満たす座席配置があれば、それを答えよ。
解法
隣接するキツネの年齢は、奇数と偶数でなければならない。
A[i]は2以上なので、偶数と偶数または奇数と奇数の和は4以上の偶数となり、素数となってしまう。
そこで、年齢が偶数のキツネと奇数のキツネで変則2部マッチングすることを考える。
- sourceから年齢が偶数のキツネに容量2の辺を張る
- 年齢が奇数のキツネからsinkに容量2の辺を張る
- 年齢が偶数のキツネから奇数のキツネに、年齢の和が素数なら容量1の辺を張る
ここに容量Nのフローが流せればよい。
年齢が偶数のキツネは2匹の年齢が奇数のキツネにフローを流すので、テーブルに座るキツネは自然と3匹以上になる。
あとは年齢が偶数・奇数のキツネの間にフローが流れている場合、そのキツネが隣接すると考えて、元の座席配置をフローから復元すればよい。
int N; int A[1010]; const int prime_max = 100000; int NP,prime[100000],divp[prime_max]; void cprime() { for(int i=2;i<prime_max;i++) if(divp[i]==0) { prime[NP++]=i; for(int j=i;j<prime_max;j+=i) divp[j]=i; } } template<class V> class MaxFlow_dinic { public: struct edge { int to,reve;V cap;}; static const int MV = 1100; vector<edge> E[MV]; int itr[MV],lev[MV]; void add_edge(int x,int y,V cap) { E[x].push_back((edge){y,(int)E[y].size(),cap}); E[y].push_back((edge){x,(int)E[x].size()-1,0}); // directed } void bfs(int cur) { MINUS(lev); queue<int> q; lev[cur]=0; q.push(cur); while(q.size()) { int v=q.front(); q.pop(); ITR(e,E[v]) if(e->cap>0 && lev[e->to]<0) lev[e->to]=lev[v]+1, q.push(e->to); } } V dfs(int from,int to,V cf) { if(from==to) return cf; ITR(e,E[from]) if(e->cap>0 && lev[from]<lev[e->to]) { V f=dfs(e->to,to,min(cf,e->cap)); if(f>0) { e->cap-=f; E[e->to][e->reve].cap += f; return f; } } return 0; } V maxflow(int from, int to) { V fl=0,tf; while(1) { bfs(from); if(lev[to]<0) return fl; ZERO(itr); while((tf=dfs(from,to,numeric_limits<V>::max()))>0) fl+=tf; } } }; vector<int> EE[201]; vector<vector<int> > V; int vis[201]; vector<int> dfs(int cur,int pre) { vector<int> v; vis[cur]=1; if(EE[cur][0]!=pre && vis[EE[cur][0]]==0) v=dfs(EE[cur][0],cur); else if(EE[cur][1]!=pre && vis[EE[cur][1]]==0) v=dfs(EE[cur][1],cur); v.push_back(cur); return v; } void solve() { int i,j,k,l,r,x,y; string s; cprime(); cin>>N; FOR(i,N) cin>>A[i]; MaxFlow_dinic<int> mf; FOR(x,N) { if(A[x]%2) mf.add_edge(0,1+x,2); if(A[x]%2==0) mf.add_edge(1+x,300,2); } FOR(x,N) FOR(y,N) if(A[x]%2 && divp[A[x]+A[y]]==A[x]+A[y]) mf.add_edge(1+x,1+y,1); if(mf.maxflow(0,300)!=N) return _P("Impossible\n"); FOR(x,N) if(A[x]%2) { FOR(y,mf.E[1+x].size()) { int to=mf.E[1+x][y].to-1; if(mf.E[1+x][y].cap==0 && divp[A[x]+A[to]]==A[x]+A[to]) { EE[x].push_back(to); EE[to].push_back(x); } } } FOR(x,N) if(vis[x]==0) V.push_back(dfs(x,-1)); _P("%d\n",V.size()); FOR(i,V.size()) { _P("%d",V[i].size()); FOR(j,V[i].size()) _P(" %d",V[i][j]+1); _P("\n"); } }
問題
2部マッチングと気づくと後はスルスル。
幸い本番割とスムーズにこれに気づけて、良い順位を取れた。
内容としても面白い問題でした。