Nowcodercontest5278 L动物森友会(网络流)

cnblogs界面

只有7天，是不是可以直接贪心啊。。。

网络流做法：

二分答案天数为

建图：

源点向连边，第天的流量上限是

对于所有让,向连上限为的边

每个向汇点连容量为

二分之后，判断是否满流即可

const int N=2e3+10,M=7*N,INF=1e9+10;

int n,m,S,T,vc;

//以下是网络流模板
struct Edge{
    int to,nxt,w;
}e[M<<1];
int head[N],ecnt;
void AddEdge(int u,int v,int w) {
    e[ecnt]=(Edge){v,head[u],w};
    head[u]=ecnt++;
}
void Link(int u,int v,int w){ AddEdge(u,v,w),AddEdge(v,u,0); }
#define erep(u,i) for(int i=head[u];~i;i=e[i].nxt)

int dis[N];
int Bfs(){
    static queue <int> que;
    rep(i,1,vc) dis[i]=INF;
    que.push(S),dis[S]=0;
    while(!que.empty()) {
        int u=que.front(); que.pop();
        erep(u,i) {
            int v=e[i].to,w=e[i].w;
            if(!w || dis[v]<=dis[u]+1) continue;
            dis[v]=dis[u]+1,que.push(v);
        }
    }
    return dis[T]<INF;
}

int Dfs(int u,int flowin) {
    if(u==T) return flowin;
    int flowout=0;
    erep(u,i) {
        int v=e[i].to,w=e[i].w;
        if(dis[v]!=dis[u]+1 || !w) continue;
        int t=Dfs(v,min(flowin-flowout,w));
        flowout+=t,e[i].w-=t,e[i^1].w+=t;
        if(flowin==flowout) break;
    }
    if(!flowout) dis[u]=0;
    return flowout;
}

int Dinic(){
    int ans=0;
    while(Bfs()) ans+=Dfs(S,INF);
    return ans;
}

int a[N][8],c[N],sum;

int Check(int mid) {
    if(m*mid<sum) return 0;
    rep(i,1,n+10) head[i]=-1; ecnt=vc=0;
    S=++vc,T=++vc;
    rep(i,1,7) Link(S,++vc,(mid/7+(mid%7>=i))*m);
    rep(i,1,n) {
        vc++;
        Link(vc,T,c[i]);
        rep(j,1,7) if(a[i][j]) Link(j+2,vc,INF);
    }
    return Dinic()==sum;
}


int main(){
    n=rd(),m=rd();
    rep(i,1,n) {
        c[i]=rd(),sum+=c[i];
        rep(j,1,rd()) a[i][rd()]=1;
    }
    // 二分答案，注意上界设定，防止边权爆int
    int l=0,r=1e9/m,res;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(Check(mid)) r=mid-1,res=mid;
        else l=mid+1;
    }
    printf("%d\n",res);
}