CS Academy No Prime Sum
問題概要
個の相異なる数字が与えられる。2つの和が素数にならないように数字を取り除くときき、最小の数と取り除く数字を答えよ。
解く前に考えていたいこと
・2つの色に彩色したい気分になった。しかし、グラフは木ではない。
・グラフがたくさんできてつらい気持ちになった。
解答
・最小頂点被覆問題。二部グラフを作成し最大流を流すことで、最小点カバーの数がわかる。
・頂点を列挙するには、 において、
から到達不能な の点 から到達可能な
を調べれば良い。
・頂点を調べるにはdfsを書けば良い、(自分はdijkstraを書いた)。
・素数にならない頂点も含めてグラフを作成し、最大流を流すと簡単に結果が得られるが、そうでないと、その頂点が使われたか判別する必要が出て来る(これでバグった)。
→ https://csacademy.com/submission/1570217/
#include<bits/stdc++.h> using ll = long long; #define int ll #define INF 1e9 #define EPS 0.0000000001 #define rep(i,n) for(int i=0;i<n;i++) #define loop(i,s,n) for(int i=s;i<n;i++) #define all(in) in.begin(), in.end() #define MAX 100000 using namespace std; typedef pair<int, int> pii; typedef pair<int,pii> piii; #define MP make_pair struct Edge{int to,cap,rev;}; bool even(int a){return !(a%2);} class Dinic{//max flow public: int n; vector<vector<Edge> >G;//[MAX]; vector<int> level,iter;//[MAX]; Dinic(int size){ n=size; G=vector<vector<Edge> >(n); } void add_Edge(int from, int to, int cap){ Edge q={to,cap,int(G[to].size())}; G[from].push_back(q); q={from,0,int(G[from].size()-1)}; G[to].push_back(q); } void bfs(int s){ level=vector<int>(n,-1); queue<int>q; level[s]=0; q.push(s); while(!q.empty()){ int v=q.front();q.pop(); for(int i=0;i<G[v].size();i++){ Edge &e=G[v][i]; if(e.cap>0&&level[e.to]<0){ level[e.to]=level[v]+1; q.push(e.to); } } } } int dfs(int v,int t, int f) { if(v==t)return f; for(int &i=iter[v];i<G[v].size();i++){ Edge &e=G[v][i]; if(level[v]>=level[e.to]||e.cap<=0) continue; int d =dfs(e.to,t,min(f,e.cap)); if(d>0){ e.cap-=d; G[e.to][e.rev].cap+=d; return d; } } return 0; } int mf(int s,int t) { int flow=0; while(1){ bfs(s); if(level[t]<0)return flow; iter=vector<int>(n); int f; while((f=dfs(s,t,INF))>0)flow+=f; } } }; class Prime{ public: vector<bool>flag; vector<int>prime; Prime(int size ){ flag = vector<bool>(size+1,true); for(int i = 2; i < size ;i++){ if(flag[i]){ for(int j = 2;i*j<size+1;j++) flag[i*j] = false; prime.push_back(i); } } } bool IsPrime(int num) {return flag[num];} int IndexOf(int index ) {return (index > prime.size()) ? INF:prime[index-1];} }; template <typename T> void show_with_brank(T a){ int cnt = 0; for (auto itr : a){ if(cnt++ != 0) cout << " "; cout << itr ; } } signed main(){ int n; cin >> n; Dinic fl(n+2); Prime prime(1e5*2); int source = n,sink = n+1; vector<int>v(n); vector<bool>used(n,false); rep(i,n) cin >> v[i]; rep(i,n)rep(j,n){ if(even(v[i]) and prime.IsPrime(v[i]+v[j])){ fl.add_Edge(i, j,1); } if(i == 0 and even(v[j])) fl.add_Edge(source,j,1); if(i == 0 and !even(v[j])) fl.add_Edge(j,sink, 1); } int res = fl.mf(source, sink); set<int>S; vector<vector<Edge>>edge = fl.G; vector<bool>visited(n+2,false); function<void(int)>dfs = [&] (int vertex){ if(visited[vertex])return; visited[vertex] = true; rep(i,edge[vertex].size()){ if(edge[vertex][i].cap)dfs(edge[vertex][i].to); } }; dfs(source); rep(i,n)if((even(v[i]) and !visited[i]) or ((!even(v[i])) and visited[i]))S.insert(v[i]); cout << res << endl; show_with_brank(S); cout << endl; }