CSAcademy Round #23 : E. No Prime Sum

これはしっかり解けきってよかった。
https://csacademy.com/contest/round-23/#task/no-prime-sum

問題

互いに異なるN個の自然数の集合が与えられる。
集合のうち、必要ならいくつかの要素を取り除き、任意の2要素の和が合成数となるようにしたい。
取り除く要素数の最小値と一例を求めよ。

解法

集合の要素を点とみなし、和が素数となる頂点間に辺を張ったグラフを考える。
ここからいくつかの頂点とそれに付随する辺を取り除き、すべての辺をなくしたい。
つまり、このグラフにおける最小点カバーを求める問題に帰着できた。

集合内の要素が互いに異なるため、奇数同士または偶数同士を選ぶと必ず4以上の偶数、すなわち合成数となる。
よって和が素数になるのは奇数と偶数の和を考える場合のみである。
そのため、このグラフは奇数と偶数に対応する点からなる二部グラフと考えることができる。

二部グラフの最小点カバーは最大マッチングの個数と一致し、またマッチング時の残余グラフから実際の点を求めることができる。
下記サイトが参考になる。
2部グラフにおける最大マッチングの個数と最小点被覆の個数の一致 - komiyamの日記

const int prime_max = 1000000;
int NP,prime[100000],divp[prime_max];
map<int,int> M;

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime[NP++]=i;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) divp[j]=i;
	}
}

int N;
int S[2020];
int vis[2020];


template<class V> class MaxFlow_Ford {
public:
	struct edge { int to,reve;V cap;};
	static const int MV = 10000;
	vector<edge> E[MV];
	int vis[MV];
	void add_edge(int x,int y,V cap,bool undir=false) {
		E[x].push_back((edge){y,(int)E[y].size(),cap});
		E[y].push_back((edge){x,(int)E[x].size()-1,undir?cap:0});
	}
	V dfs(int from,int to,V cf) {
		V tf;
		if(from==to) return cf;
		vis[from]=1;
		FORR(e,E[from]) if(vis[e.to]==0 && e.cap>0 && (tf = dfs(e.to,to,min(cf,e.cap)))>0) {
			e.cap -= tf;
			E[e.to][e.reve].cap += tf;
			return tf;
		}
		return 0;
	}
	V maxflow(int from, int to) {
		V fl=0,tf;
		while(1) {
			ZERO(vis);
			if((tf = dfs(from,to,numeric_limits<V>::max()))==0) return fl;
			fl+=tf;
		}
	}
};


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	
	cin>>N;
	
	MaxFlow_Ford<int> mf;
	FOR(i,N) {
		cin>>S[i];
		if(S[i]%2==0) mf.add_edge(0,i+1,1);
		else mf.add_edge(i+1,2002,1);
	}
	
	FOR(x,N) FOR(y,N) if(divp[S[x]+S[y]]==0 && S[x]%2==0 && S[y]%2==1) mf.add_edge(x+1,y+1,1);
	mf.maxflow(0,2002);
	
	set<int> V;
	
	vis[0]=1;
	queue<int> Q;
	Q.push(0);
	while(Q.size()) {
		x=Q.front();
		Q.pop();
		
		V.insert(x);
		FORR(r,mf.E[x]) if(vis[r.to]==0 && r.cap>0) vis[r.to]=1, Q.push(r.to);
	}
	
	set<int> R;
	FOR(x,N) if(((S[x]%2==0) ^ (V.count(x+1)==0))==0) R.insert(S[x]);
	
	cout<<R.size()<<endl;
	FORR(r,R) cout<<r<<" ";
	cout<<endl;
}

まとめ

二部グラフの点カバー問題にさっと持ち込めたのは良かった。