题目大意
一个物品有三个属性 : 价值,键值,等级.
你不能选取等级高于(level)的物品,键值之和为质数的两个数字不共存.
问最低的等级使得可以选出价值之和超过(k)的物品.
(nleq 100, 1 leq ext{键值} leq n)
题解
首先考虑二分答案.
这样可以去掉物品等级的限制.
我们很容易发现除了(2)的所有偶数都是非质数.
什么意思呢 ?
如果我们不考虑(1)这个神奇的数字，那么按照排斥关系建边会发现这构成了一张二分图．
所以可以直接用最小割经典模型解决．
那么现在考虑一下(1)这个神奇的数字．
我们发现只有(1+1)会得到(2)．
所以我们可以对(1)进行特殊处理．
因为我们知道只能在所有的(1)中选取出一个(1)．
所以我们可以找到价值最大的(1)进行建图．
复杂度(O( ext{网络流}))
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
#define rg register int
#define rep(i,a,b) for(rg i=(a);i<=(b);++i)
#define per(i,a,b) for(rg i=(a);i>=(b);--i)
const int maxn = 128;
const int maxnum = 200010;
const int inf = 0x3f3f3f3f;
int pri[maxnum],pri_cnt;bool vis[maxnum];
void liner(int n){
vis[1] = true;
rep(i,2,n){
if(!vis[i]) pri[++pri_cnt] = i;
rep(j,1,pri_cnt){
ll x = 1LL*i*pri[j];
if(x > n) break;
vis[x] = true;
if(i % pri[j] == 0) break;
}
}
}
struct Edge{
int to,next,cap;
}G[maxn*(maxn+4)];
int head[maxn],cnt = 1;
void add(int u,int v,int c){
G[++cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt;
G[cnt].cap = c;
}
inline void insert(int u,int v,int c){
//printf("edge %d -> %d : (%d)
",u,v,c);
add(u,v,c);add(v,u,0);
}
#define v G[i].to
int q[maxn],l,r,dis[maxn];
int S,T;
bool bfs(){
memset(dis,-1,sizeof dis);
l = 0;r = -1;q[++r] = S;
dis[S] = 0;
while(l <= r){
int u = q[l++];
for(rg i = head[u];i;i=G[i].next){
if(dis[v] == -1 && G[i].cap){
dis[v] = dis[u] + 1;
q[++r] = v;
}
}
}return dis[T] != -1;
}
int dfs(int u,int f){
if(u == T || f == 0) return f;
int ret = 0;
for(rg i = head[u];i;i=G[i].next){
if(dis[v] == dis[u] + 1 && G[i].cap){
int x = dfs(v,min(G[i].cap,f));
ret += x;f -= x;
G[i].cap -= x;
G[i^1].cap += x;
if(f == 0) break;
}
}return ret;
}
inline int dinic(){
int ret = 0;
while(bfs()) ret += dfs(S,inf);
return ret;
}
#undef v
struct Node{
int p,c,l;
Node(){}
Node(const int &a,const int &b){
p = a;c = b;
}
}a[maxn];
inline bool cmp(const Node &a,const Node &b){
return a.l < b.l;
}
int sta[2][maxn],top[2],val = 0,max1 = 0;
int nod[2][maxn],nodecnt;
inline void insert(const Node &x){
val += x.p;++ nodecnt;
if(x.c & 1){
insert(nodecnt,T,x.p);
rep(i,1,top[0]){
if(vis[x.c + sta[0][i]] == false){
insert(nod[0][i],nodecnt,inf);
}
}
sta[1][++top[1]] = x.c;
nod[1][top[1]] = nodecnt;
}else{
insert(S,nodecnt,x.p);
rep(i,1,top[1]){
if(vis[x.c + sta[1][i]] == false){
insert(nodecnt,nod[1][i],inf);
}
}
sta[0][++top[0]] = x.c;
nod[0][top[0]] = nodecnt;
}
}
int n,k;
inline bool check(int mid){
top[0] = top[1] = 0;max1 = 0;
memset(head,0,sizeof head);
cnt = 1;val = 0;nodecnt = 0;
S = ++ nodecnt;T = ++ nodecnt;
int max1 = 0;
rep(i,1,n){
if(a[i].l <= mid && a[i].c != 1) insert(a[i]);
if(a[i].l <= mid && a[i].c == 1){
max1 = max(max1,a[i].p);
}
}
if(max1 != 0) insert(Node(max1,1));
val -= dinic();
return val >= k;
}
int main(){
read(n);read(k);
liner(200000);
rep(i,1,n){
read(a[i].p);read(a[i].c);read(a[i].l);
}sort(a+1,a+n+1,cmp);
int l = 1,r = n,ans = -1;
while(l <= r){
int mid = l+r >> 1;
if(check(mid)) ans = mid,r = mid-1;
else l = mid+1;
}printf("%d
",ans);
return 0;
}