Codeforces ECR #021 : F. Card Game

これ系久々に見たので思い出せなかった。
http://codeforces.com/contest/808/problem/F

問題

N枚のカードがあり、それぞれパワーP[i]、マジックナンバーC[i]、レベルL[i]が設定されている。

以下の条件を満たすようカードのsubsetを作りたい。
必要な自身の最小レベルを求めよ。

• カードのパワーの総和がK以上
• subset中2枚のカードのマジックナンバーの和は合成数
• 各カードのレベルは自身のレベル以下

解法

自身のレベルが増えるほど使えるカードが増える。
よって自身のレベルは大きいほどよいので、二分探索で下限を求めることを考えよう。
そうすると3つ目の条件は以後考えなくてよくなる。

2つ目の条件を先に考える。
2つの正整数の和が素数になるのは、1+1を除けば奇数+偶数のケースのみである。
よってC[i]が偶数のカード群と奇数のカード群にに分けよう。

2つのグループのうち、同時に取れない条件があり、その範囲で何かしらのパラメータの総和を最大化する。
…となると、グラフのフローの最小カットを用いるいわゆる燃やす埋める問題に帰着できる。

よって、sourceから(自身のレベル以下の)偶数カード群に容量P[i]の辺を張り、同じく奇数カード群からsinkに容量P[i]の辺を張ろう。
偶数カードから奇数カードへは、C[i]の和が素数である場合に辺を張る。
なお、奇数カード群でもC[i]=1となるカードは2枚以上選択できないので、P[i]が最大のもののみ1つ用いるようにしよう。

あとは(自身のレベル以下の)P[i]の総和から、フローの最小カット＝最大フロー分を引き、それがK以上かどうか判定すればよい。

int N,K;
int P[101],C[101],L[101];

template<class V> class MaxFlow_Ford {
public:
	struct edge { int to,reve;V cap;};
	static const int MV = 102;
	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;
		}
	}
};

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) {
		prime[NP++]=i;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) divp[j]=i;
	}
}


int ok(int val) {
	int i,j;
	MaxFlow_Ford<ll> mf;
	ll tot=0;
	FOR(i,N) if(L[i]<=val && C[i]!=1) {
		tot+=P[i];
		if(C[i]%2==0) {
			mf.add_edge(100,i,P[i]);
			FOR(j,N) if(C[j]%2==1 && divp[C[i]+C[j]]==0) {
				mf.add_edge(i,j,1LL<<60);
			}
		}
		else mf.add_edge(i,101,P[i]);
	}
	
	int id=-1;
	FOR(i,N) if(C[i]==1 && L[i]<=val && (id==-1 || P[i]>P[id]) ) id=i;
	if(id>-1) {
		tot+=P[id];
		mf.add_edge(id,101,P[id]);
	}
	
	return tot-mf.maxflow(100,101)>=K;
}

まとめ

二部グラフまで思いついたのに、「フローと総和はうまく合わないな」と考えて燃やす埋める問題を忘れていた。