考试的时候花了好久来调这道题，结果忘了1的特判就gg了。但自己二分也确实有问题，建边也不是特别优。但基本的想法是没啥问题的。 就是二分一个等级，然后对符合条件的符卡建一个最大权闭合图，判断是否合法，再一次缩小答案的区间。 每次也不用想太多，直接重新拆了暴力建边就可以了23333之前以为这样会T掉，然而23333只要不是完全暴力（每次再重新判断两个的和是不是质数）（这个也只会t掉10%的点而已）都能过。 关于建图。 这是一个二分图，奇数放一边，偶数放一边。每一边的任意两个数的和都是偶数，肯定相加不是质数。每次二分等级level 后，选出符合这个等级的点来建图。（加入这个图的边一定已经满足等级<=level了）s向选出的每个偶数连一条流量为它的火力的边，每个偶数u向等级<=level且它们时间和为质数的奇数连一条inf的边，表示这两个必须有取舍，每个奇数再向t连一条流量为火力的边。 其实就是最大权闭合子图。 看起来似乎特别完美。 但： 1的特判！1的特判！1的特判！ 无论这里面有多少个T等于1的点，我们都只能选其中的一个。所以每次找出符合level限制的火力最大的一个1（有点贪心的思想吧）加入图中。
#include<cstdio> #include<cstring> #include<ctime> #include<algorithm> #define ms(x,y) memset(x,y,sizeof(x)) using namespace std; const int N = 400 + 10; const int M = 1e6 + 10; const int INF = 0x73f3f3f * 4; int n,k; int p[N],T[N],l[N]; int mmax=-1,mmin=0x73f3f3f; int zzz=-1,lev; struct node{ int pre,v; int f; }edge[M]; int num=1; int head[N],cur[N]; void addedge(int from,int to,int f){ num++; edge[num].pre=head[from]; edge[num].v=to; edge[num].f=f; head[from]=num; num++; edge[num].pre=head[to]; edge[num].v=from; edge[num].f=0; head[to]=num; } int cnt=0,primes[M]; bool isnot[M]; void Prime(){ memset(isnot,0,sizeof(isnot)); isnot[1]=true; for(int i=2;i<=M - 10;i++){ if(!isnot[i]){ cnt++; primes[cnt]=i; } for(int j=1;j<=cnt;j++){ int u=i*primes[j]; if(u>M-10) break; isnot[u]=true; if(i%primes[j]==0) break; } } } int number[N][2]; int s,t; int dis[N],state[M]; bool vis[N]; bool bfs(){ int h=0,tail=1; dis[s]=0,vis[s]=true; state[1]=s; do{ h++; int u=state[h]; for(int i=head[u];i;i=edge[i].pre){ int v=edge[i].v; if(!vis[v]&&edge[i].f){ dis[v]=dis[u]+1; vis[v]=true; tail++; state[tail]=v; } } }while(h<tail); if(vis[t]==true) return true; return false; } inline int Min(int a,int b){ return a<b?a:b; } inline int Max(int a,int b){ return a>b?a:b; } int dfs(int u,int delta){ if(u==t||delta==0) return delta; int ans=0; for(int i=head[u];i&δi=edge[i].pre){ int v=edge[i].v; if(edge[i].f&&dis[v]==dis[u]+1){ int dd=dfs(v,Min(delta,edge[i].f)); edge[i].f-=dd; edge[i^1].f+=dd; ans+=dd; delta-=dd; } } if(!ans) dis[u]=-1; return ans; } #define ms(x,y) memset(x,y,sizeof(x)) void zero(){ ms(dis,0);ms(vis,0);ms(state,0); } int maxflow(){ int ans=0; while(1){ zero(); if(!bfs()) break; ans+=dfs(s,INF); } return ans; } bool check1(int x){ for(int i=1;i<=cnt;i++){ if(x%primes[i]==0) return false; if(primes[i]*primes[i]>x) break; } return true; } int numb[N][N]; void noname(){ ms(numb,0); for(int i=1;i<=number[0][0];i++){ for(int j=1;j<=number[0][1];j++){ int u=number[i][0],v=number[j][1]; if(T[u]+T[v]<M-10){ if(isnot[T[u]+T[v]]==false){ numb[u][v]=1; } } else if(check1(T[u]+T[v])) numb[u][v]=1; } } } int zx=0; bool check(int mid){ num=1,ms(head,0),zx=0,zzz=-1; for(int i=1;i<=number[0][0];i++){ for(int j=1;j<=number[0][1];j++){ int u=number[i][0],v=number[j][1]; if(l[u]>mid||l[v]>mid||T[v]==1) continue; if(numb[u][v]==1) addedge(u,v,INF); } } for(int i=1;i<=number[0][0];i++){ if(l[number[i][0]]<=mid){ addedge(s,number[i][0],p[number[i][0]]); zx+=p[number[i][0]]; } } for(int i=1;i<=number[0][1];i++){ if(T[number[i][1]]==1){ if(l[number[i][1]]>mid) continue; if(zzz<p[number[i][1]]){ zzz=p[number[i][1]]; lev=number[i][1]; } continue; } if(l[number[i][1]]<=mid){ addedge(number[i][1],t,p[number[i][1]]); zx+=p[number[i][1]]; } } if(zzz!=-1){ for(int i=1;i<=number[0][0];i++){ int u=number[i][0]; if(numb[u][lev]==1) addedge(u,lev,INF); } zx+=zzz; addedge(lev,t,zzz); } int xx=maxflow(); xx=zx-xx; if(xx<k) return false; return true; } int main(){ freopen("card.in","r",stdin); freopen("card.out","w",stdout); scanf("%d%d",&n,&k); s=0,t=n+1; Prime(); for(int i=1;i<=n;i++){ scanf("%d%d%d",&p[i],&T[i],&l[i]); number[0][(T[i]&1)]++; number[number[0][T[i]&1]][T[i]&1]=i; mmax=Max(mmax,l[i]); mmin=Min(mmin,l[i]); } noname(); if(!check(mmax)){ printf("-1\n");return 0;} int L=mmin,R=mmax; while(L<R){ num=1,ms(head,0); int mid=(L+R)>>1; if(check(mid)) R=mid; else L=mid+1; } printf("%d",R); return 0; }