nas可做网站服务器吗/友情链接例子

2017 CCPC 秦皇岛 H Prime Set ZOJ 3988

题意：给一个数组，对于每两个数加起来为素数那么就是一个集合，求不超过k个集合的最多数是多少？
思路：很容易想到n^2建边跑最大匹配，出现两个问题：
1.两个集合中可能出现相同元素，这样最大匹配不是答案（比如：样例2）
2.素数=奇数+偶数（奇偶建边），但是特例：1+1=2

Solution:
1.对于第一个问题，我们假设跑出来的最大匹配是ans,
那么会有ans * 2个不重复元素，k-ans个和前面重复的和k-ans和前面不重复的，答案就是ans*2+k-ans,注意：这里可能会算多，要和暴力跑的能加入set的取最小值（看样例2自行理解）
2.跑1的时候特殊处理，我们先跑正常的，跑出来之后把1连的边加入再跑一次，剩下的cnt/2就是1和1自己匹配的个数。

Hint:
Code:

/*
▄███████▀▀▀▀▀▀███████▄
░▐████▀▒▒▒▒▒▒▒▒▒▒▀██████▄
░███▀▒▒▒ACCEPTED▒▒▒▒▀█████
░▐██▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒████▌
░▐█▌▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒████▌
░░█▒▄▀▀▀▀▀▄▒▒▄▀▀▀▀▀▄▒▐███▌
░░░▐░░░▄▄░░▌▐░░░▄▄░░▌▐███▌
░▄▀▌░░░▀▀░░▌▐░░░▀▀░░▌▒▀▒█▌
░▌▒▀▄░░░░▄▀▒▒▀▄░░░▄▀▒▒▄▀▒▌
░▀▄▐▒▀▀▀▀▒▒▒▒▒▒▀▀▀▒▒▒▒▒▒█
░░░▀▌▒▄██▄▄▄▄████▄▒▒▒▒█▀
░░░░▄██████████████▒▒▐▌
░░░░▀███▀▀████▀█████▀▒▌
░░░░░▌▒▒▒▄▒▒▒▄▒▒▒▒▒▒▐
░░░░░▌▒▒▒▒▀▀▀▒▒▒▒▒▒▒▐*/
#include<bits/stdc++.h>
#include<tr1/unordered_map>
using namespace std;
typedef long long ll;
const int INF=1e9+7;
const int N=3e3+5;
const int M=5e6+5;
int n,m,s,t,maxflow=0,lowflow;
struct node {int to,w,next;
} edge[M];
int head[N],cnt=1,dep[N],inque[N],cur[N];
void add(int u,int v,int w) {edge[++cnt].next=head[u];edge[cnt].to=v;edge[cnt].w=w;head[u]=cnt;
}
struct Maxflow {bool bfs() {queue<int>q;memset(dep,-1,sizeof dep);dep[s]=0;q.push(s);while(!q.empty()) {int u=q.front();q.pop();inque[u]=0;for(int i=head[u]; i; i=edge[i].next) {int v=edge[i].to,w=edge[i].w;if(dep[v]==-1&&w) {dep[v]=dep[u]+1;q.push(v);}}}return dep[t]!=-1;}int dfs(int u,int flow) {if(u==t) {return flow;}int rlow=0,used=0;for(int i=cur[u]; i; i=edge[i].next) {int v=edge[i].to,w=edge[i].w;if(w&&dep[v]==dep[u]+1) {if(rlow=dfs(v,min(flow,w))) {used+=rlow;flow-=rlow;edge[i].w-=rlow;edge[i^1].w+=rlow;if(flow==0)break;}}}if(!used)dep[u]=-1;return used;}int Dinic() {maxflow=0;while(bfs()) {for(int i=1; i<=n+3; i++)cur[i]=head[i];maxflow+=dfs(s,INF);}return maxflow;}void init() {cnt=1;memset(head,0,sizeof head);}void addedge(int u,int v,int w) {add(u,v,w);add(v,u,0);}
} ac;
const int MAXN=2e6+5;
int prime[MAXN+1],a[N],k;
bool vis[MAXN+10];
void getPrime() {for(int i=2; i<=MAXN; i++) {if(!prime[i])prime[++prime[0]]=i;for(int j=1; j<=prime[0]&&prime[j]<=MAXN/i; j++) {prime[prime[j]*i]=1;if(i%prime[j]==0) break;}}for(int i=1; i<=prime[0]; i++)vis[prime[i]]=1;
}
int cal() {int ans=0;for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {if(i!=j&&vis[a[i]+a[j]]) {ans++;break;}}}return ans;
}
int solve() {ac.init();s=n+1,t=n+2;for(int i=1; i<=n; i++) {if((a[i]&1)&&a[i]!=1)ac.addedge(s,i,1);if(a[i]%2==0)ac.addedge(i,t,1);}for(int i=1; i<=n; i++) {if((a[i]&1)&&a[i]!=1) {for(int j=1; j<=n; j++) {if(a[j]%2==0&&vis[a[i]+a[j]])ac.addedge(i,j,1);}}}int num1=ac.Dinic();int pos1=n+3,cnt1=0;for(int i=1; i<=n; i++)cnt1+=(a[i]==1);ac.addedge(s,pos1,cnt1);for(int i=1; i<=n; i++) {if(a[i]%2==0&&vis[a[i]+1])ac.addedge(pos1,i,1);}int num2=ac.Dinic();cnt1=(cnt1-num2)/2;int ans=cnt1+num1+num2;if(ans>=k)return k*2;return min(ans*2+k-ans,cal());
}
int main() {getPrime();int T;cin>>T;while(T--) {scanf("%d%d",&n,&k);for(int i=1; i<=n; i++)scanf("%d",&a[i]);printf("%d\n",solve());}
}