CF 808F
看到最小的level，我们可以选择二分答案，然后建图就是把所有的卡片按照奇偶进行二分图，因为要产生质数只可能是奇数+偶数，所以我们这里把能产生质数的两张卡进行连边，流量就是INF，跑最大流，获得的就是可以丢弃的最大p，那么最小的p就是sum-p了
struct node{
int p,c,l;
};
struct Dinic
{
struct Edge
{
int from,to,cap,flow;
Edge(int f,int t,int c,int w):from(f),to(t),cap(c),flow(w){}
};
int n,m,s,t;//size of point and line and the start point and end point
vector<int>d,cur;
vector<bool>vis;
vector<Edge>E;
vector<vector<int>>G;
const int INF=0x3f3f3f3f;
Dinic(int n,int m):n(n),m(m)
{
d.resize(n+1);
vis.resize(n+1,false);
G.resize(n+1);
cur.resize(n+1);
}
void add_edge(int from,int to,int cap)
{
E.push_back({from,to,cap,0});
G[from].push_back(E.size()-1);
E.push_back({to,from,0,0});
G[to].push_back(E.size()-1);
}
bool bfs()//get the depth of every point
{
fill(vis.begin(),vis.end(),false);
queue<int>q;
q.push(s);
d[s]=0;
vis[s]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0;i<G[x].size();++i)
{
auto& e=E[G[x][i]];
if(!vis[e.to]&&e.cap>e.flow)
{
vis[e.to]=1;
d[e.to]=d[x]+1;
q.push(e.to);
}
}
}
return vis[t];
}
ll dfs(int x,int a)
{
if(x==t||a==0)return a;
ll res=0,f;
for(int& i=cur[x];i<G[x].size();++i)
{
auto& e=E[G[x][i]];
if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0)
{
e.flow+=f;
E[G[x][i]^1].flow-=f;
res+=f;
a-=f;
if(a<=0)break;
}
}
return res;
}
ll maxflow(int s,int t)
{
this->s=s;
this->t=t;
ll ans=0;
while(bfs())
{
fill(cur.begin(),cur.end(),0);
ans+=dfs(s,INF);//INF is the now flow
}
return ans;
}
};
void solve(){
int n,k;
cin>>n>>k;
vector<node>cards(n+1);
int l=INT_MAX,r=INT_MIN;
for(int i=1;i<=n;++i){
cin>>cards[i].p>>cards[i].c>>cards[i].l;
l=min(l,cards[i].l);
r=max(r,cards[i].l);
}
auto check_prime=[&](int num){
for(int i=2;i<=sqrt(num);++i){
if(num%i==0)return 0;
}
return 1;
};
auto check=[&](int mini_level){
int S=n+1,T=n+2;
int maxp_one=-1;
for(int i=1;i<=n;++i){
if(cards[i].c==1&&cards[i].l<=mini_level){
maxp_one=max(maxp_one,cards[i].p);
}
}
ll sum=0;
bool one_flag=false;
vector<int>choosed;
for(int i=1;i<=n;++i){
if((cards[i].l<=mini_level&&cards[i].c!=1)||(cards[i].c==1&&cards[i].p==maxp_one&&!one_flag)){
if(cards[i].c==1){
one_flag=true;
}
choosed.push_back(i);
sum+=cards[i].p;
}
}
Dinic dinic(n+3,0);
for(int i=0;i<choosed.size();++i){
if(cards[choosed[i]].c&1){
dinic.add_edge(S,choosed[i],cards[choosed[i]].p);
}else{
dinic.add_edge(choosed[i],T,cards[choosed[i]].p);
}
for(int j=i+1;j<choosed.size();++j){
if(check_prime(cards[choosed[i]].c+cards[choosed[j]].c)){
if(cards[choosed[i]].c&1)dinic.add_edge(choosed[i],choosed[j],INF);
else dinic.add_edge(choosed[j],choosed[i],INF);
}
}
}
auto maxflow=dinic.maxflow(S,T);
return sum-maxflow>=k;
};
int ans=-1;
while(l<=r){
int m=(l+r)>>1;
if(check(m)){
r=m-1;
ans=m;
}else{
l=m+1;
}
}
cout<<ans<<'\n';
return;
}
CF 510E
和上面的做法类似，不过这次我们需要保存是质数的两只狐狸，原点向奇数狐狸连线(cap=2)，然后奇数狐狸向产生质数的偶数狐狸连线(cap=1)，然后偶数狐狸向汇点连线(cap=2)，看最大流是不是n，如果是那么就是可分的，然后我们按着奇数->偶数有边，遍历我们的图，把每一桌的狐狸给整进去就可以了。老子的板子好像开始有点问题，调了贼几把久。
struct Dinic
{
struct Edge
{
int from,to;
ll cap;
Edge(int f,int t,int c):from(f),to(t),cap(c){}
};
int n,m,s,t;//size of point and line and the start point and end point
vector<int>d,cur;
vector<bool>vis;
vector<Edge>E;
vector<vector<int>>G;
const int INF=0x3f3f3f3f;
Dinic(int n,int m):n(n),m(m)
{
d.resize(n+1);
vis.resize(n+1,false);
G.resize(n+1);
cur.resize(n+1);
}
void add_edge(int from,int to,int cap)
{
E.push_back({from,to,cap});
G[from].push_back(E.size()-1);
E.push_back({to,from,0});
G[to].push_back(E.size()-1);
}
bool bfs()//get the depth of every point
{
fill(vis.begin(),vis.end(),false);
queue<int>q;
q.push(s);
d[s]=0;
vis[s]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0;i<G[x].size();++i)
{
auto& e=E[G[x][i]];
if(!vis[e.to]&&e.cap)
{
vis[e.to]=1;
d[e.to]=d[x]+1;
q.push(e.to);
}
}
}
return vis[t];
}
ll dfs(int x,ll a)
{
if(x==t||a==0)return a;
ll res=0,f;
for(int& i=cur[x];i<G[x].size();++i)
{
auto& e=E[G[x][i]];
if(d[x]+1==d[e.to]&&e.cap)
{
int f=dfs(e.to,min(a-res,e.cap));
e.cap-=f;
E[G[x][i]^1].cap+=f;
res+=f;
if(res==a)break;
}
}
return res;
}
ll maxflow(int s,int t)
{
this->s=s;
this->t=t;
ll ans=0;
while(bfs())
{
fill(cur.begin(),cur.end(),0);
ans+=dfs(s,INF);//INF is the now flow
}
return ans;
}
};
void solve(){
int n;
cin>>n;
vector<int>f(n+1);
for(int i=1;i<=n;++i)cin>>f[i];
auto check_prime=[&](int num){
for(int i=2;i<=sqrt(num);++i){
if(num%i==0){
return 0;
}
}
return 1;
};
Dinic dinic(n+3,0);
int S=0,T=n+1;
auto check=[&](){
vector<int>odd,even;
for(int i=1;i<=n;++i){
if(f[i]&1){
odd.push_back(i);
dinic.add_edge(S,i,2);
}else{
even.push_back(i);
dinic.add_edge(i,T,2);
}
}
for(int i=0;i<odd.size();++i){
for(int j=0;j<even.size();++j){
if(check_prime(f[odd[i]]+f[even[j]])){
dinic.add_edge(odd[i],even[j],1);//odd->even
}
}
}
auto maxflow=dinic.maxflow(S,T);
return maxflow==n;
};
//first checkout whether it is possible to arrange all foxes
if(!check()){
cout<<"Impossible\n";
return;
}
vector<vector<int>>groups;
//then we use dfs to arrange all foxes
vector<int>vis(n+1);
function<void(int)>dfs=[&](int cur){
groups.back().push_back(cur);
vis[cur]=1;
for(int id:dinic.G[cur]){
auto e=dinic.E[id];
if(e.to==S||e.to==T||vis[e.to])continue;
if((e.cap==0&&f[e.from]%2==1)||(dinic.E[id^1].cap==0&&f[e.to]%2==1)){
dfs(e.to);
}
}
};
for(int i=1;i<=n;++i){
if(!vis[i]){
groups.push_back(vector<int>());
dfs(i);
}
}
cout<<groups.size()<<'\n';
for(int i=0;i<groups.size();++i){
cout<<groups[i].size()<<' ';
for(int num:groups[i]){
cout<<num<<' ';
}
cout<<'\n';
}
return;
}