题解 CF628F 【Bear and Fair Set】

· · 题解

乍一看，什么破题目，根本不可做！

实际上，是网络流，建图比较毒瘤，建议紫题或以上，标签最大流。

（数组含义以英文题面为准）

为了方便，我们添加两组新的限制：

upTo_0=0,quantity_0=0$以及$upTo_{q+1}=b,quantity_{q+1}=n

之后，将q改变为q+1（因为添加了原来的第q+1组限制）。

这个时候，我们就可以将集合分成q段。对\forall i \in [1,q]，第i段中有(quantity_i-quantity_{i-1})个值域在(upTo_{i-1},upTo_i]的数。

这时候就可以建图了。

前置知识：在区间(i,j]中，模5余k的数有(j-k)/5-(i-k)/5个，其中/是整除符号。

设id_i为表示模5余i的节点的虚拟节点。

则从源点S，我们向每个i连quantity_i单位流量；

再从每个i，向每个id_j，连 (upTo_{i-1},upTo_i]中模5余j的数的数量 的流量

最后从每个id_i向汇点T连n/5的流量

之后跑最大流即可。如果最大流不是n，则不合法。

代码：

#include<bits/stdc++.h>
using namespace std;
pair<int,int>p[10100];
int n,lim,m,head[20100],cur[20100],dep[20100],cnt,id[5],S,T,res;
struct node{
    int to,next,val;
}edge[200100];
void ae(int u,int v,int w){
    edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
    edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=0,head[v]=cnt++;
}
int calc(int L,int R,int mod){//Calculate the number of (%5=mod)'s nums in range (i,j] 
    R=R-mod+5,L=L-mod+5;
    return R/5-L/5;
}
bool reach;
queue<int>q;
bool bfs(){
    memset(dep,0,sizeof(dep)),dep[S]=1,q.push(S);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=cur[x]=head[x];i!=-1;i=edge[i].next)if(edge[i].val&&!dep[edge[i].to])dep[edge[i].to]=dep[x]+1,q.push(edge[i].to);
    }
    return dep[T]>0;
}
int dfs(int x,int flow){
    if(x==T){reach=true;res+=flow;return flow;}
    int used=0;
    for(int &i=cur[x];i!=-1;i=edge[i].next){
        if(!edge[i].val||dep[edge[i].to]!=dep[x]+1)continue;
        int ff=dfs(edge[i].to,min(flow-used,edge[i].val));
        if(ff){
            edge[i].val-=ff;
            edge[i^1].val+=ff;
            used+=ff;
            if(used==flow)break;
        }
    }
    return used;
}
int main(){
    scanf("%d%d%d",&n,&lim,&m),memset(head,-1,sizeof(head));
    S=n+6,T=n+7;
    for(int i=0;i<5;i++)id[i]=n+i+1,ae(id[i],T,n/5);
    for(int i=1;i<=m;i++)scanf("%d%d",&p[i].first,&p[i].second);
    sort(p+1,p+m+1),m++,p[m]=make_pair(lim,n);
    for(int i=1;i<=m;i++)if(p[i].first-p[i-1].first<p[i].second-p[i-1].second||p[i].second<p[i-1].second){puts("unfair");return 0;}//if there are more numbers than the range, or in a larger range there's a smaller total,it is definitelt invalid. 
    for(int i=1;i<=m;i++)ae(S,i,p[i].second-p[i-1].second);
    for(int i=1;i<=m;i++)for(int j=0;j<5;j++)ae(i,id[j],calc(p[i-1].first,p[i].first,j));
    while(bfs()){
        reach=true;
        while(reach)reach=false,dfs(S,0x3f3f3f3f);
    }
//  printf("%d\n",res);
    puts(res==n?"fair":"unfair");
    return 0;
}