P2823 时间表 题解

未来姚班zyl · 2023-06-29 12:02:07 · 题解

前言：这是一道纯网络瘤流

题目大意

题目十分长，但有许多废话，看了老久才大概知道意思。去掉没用的信息，这题的大意如下（替换掉了一些原题中的字母，方便理解以及阅读俺的代码）：

有一个公司，共 n 人。这些要工作 day 天，每天长 hour 小时。

工作分为两类：打电话，开会。

现在有如下的两大类限制：

• 对员工的限制

  1. 一位员工在同一小时内只能做一份工作，或者摸鱼休息。

  2. 总共只能打 L_{i} 小时电话。

  3. 每个人每天最多工作 N 小时。

  4. 在某些小时，某个人必须参加会议。

  5. 在午休时间 [l,r] 中，必须休息一个小时。

• 对工作的限制：第 i 天的第 j 小时，必须有 need_{i,j} 个人选择打电话。

然后就会发现，原题中有不少信息与这题毫无关系。（有研究项目肯定研究自己的，所以将其视为休息）。

题目分析

把题意概括出来后，题目就很繁琐简单了。只需对每个限制依次处理了。

小技巧：如果碰到限制条件多的网络流题目，在纸上按限制条件左右分层（方便连边），按元素上下分层（方便建点），画出草图。

像这题，可以按照下图分层：

其中，lim\ A_{i} 对应了对员工的限制，lim\ B 对应对工作的限制，红线代表按人分，绿线代表按边分，紫线代表按小时分。

至于没有写出的两条限制，lim\ A_1 是本题的运作原理，lim\ A_4 将贯穿加边的过程。

至于为什么要这样分，往下看。

现在，根据上面的草图，从左往右一层一层开始建图开始建图。首先要知道，由于工作只对打电话给出限制，所以会议能不去就不去，建图以打电话的工作为中心，这同时也是 lim\ A_4 不列出来分层的原因。

• 第一层，新建 n 个点，编号 1\sim n，代表了员工 i，由原点向点 i 连流量为 L_i 的边。
• 第二层，新建 n\times day 个点，编号 (n+1)\sim (n+n\times day)，我们暂时用 Id_{i,j} 表示这一层中，第 i 个人在第 j 天的打电话工作（类似的表示将在后面讲述如何设计具体数值）。由于 lim\ A_4 的存在，我们用 N 减去这一天的会议总数，就能得到这一天最多能打多少小时电话，设其为 x，则点 i 向点 Id_{i,j} 连流量为 x 的边。
• 第三层，新建 2\times n\times day 个点，编号 (n+n\times day+1)\sim(n+3\times n\times day)，设 Idrest_{i,j} 表示第 i 个人在第 j 天的午休段的打电话工作，Idwork_{i,j} 表示非午休段的打电话工作。前者只需用午休段的总时间减去期间会议的数量再减去休息的一个小时，设为 x，后者只需用总时间减去午休段的时间减去除午休外的会议的数量，设为 y。则点 Id_{i,j} 向 Idrest_{i,j} 连流量为 x 的边，向 Idwork_{i,j} 连流量为 y 的边。
• 第四层，新建 day\times hour 个点，编号 (n+3\times n\times day+1)\sim(n+3\times n\times day+day\times hour)，设 Idcall_{i,j} 为第 i 天第 j 小时的打电话工作，则将其向汇点连流量为 need_{i,j} 的边。对于午休时间段，如果第 k 个人没有会议，则点 Idrest_{k,i} 向 Idcall_{i,j} 连流量为 1 的边，对于非午休时间段，就由 Idwork_{k,i} 连。

建图就到这里了，对于这么多编号，可以发现，我们建的点依次组成矩形，可以用点在当前矩形中的标号加上之前的点的总数，这样编号就不重复了，具体可以看代码。

对于判定有无解，如果出现了边权小于 0，则说明有人超过了工作量限制，肯定无解。否则，最大流等于 \sum\limits_{1\le i\le day,1\le j\le hour}need_{i,j} 则有解，否则无解。

#include<bits/stdc++.h>
#define ll long long
#define L x<<1
#define R x<<1|1
#define mid (l+r>>1)
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define ull unsigned long long
#define ui unsigned int
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57) {if(c=='-') w=-1;c=getchar();}while(c>=48&&c<=57) s=(s<<1)+(s<<3)+c-48,c=getchar();return s*w;}
inline void pf(ll x){if(x<0) putchar('-'),x=-x;if(x>9)pf(x/10);putchar(x%10+48);}
const int N =2.2e4+5,M=4e7+5,inf=2147000000;
using namespace std;
int n,m,s,t,sum,h[N],nxt[M],now[N],to[M],cnt=1,dep[N];ll w[M],ans;
inline void add(int a,int b,ll c){
    to[++cnt]=b,nxt[cnt]=h[a],h[a]=cnt,w[cnt]=c;
    to[++cnt]=a,nxt[cnt]=h[b],h[b]=cnt,w[cnt]=0;
}
inline bool bfs(){
    queue<int>q;
    memset(dep,-1,sizeof(dep));
    dep[s]=0,q.push(s),now[s]=h[s];
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=h[x];i;i=nxt[i]){
            int y=to[i];
            if(w[i]==0||dep[y]!=-1)continue;
            dep[y]=dep[x]+1,q.push(y),now[y]=h[y];
            if(y==t)return 1;
        }
    }
    return 0;
}
inline int dfs(int x,ll lim){
    if(x==t)return lim; 
    ll k,tmp=0;
    for(int i=now[x];i&&lim;i=nxt[i]){
        now[x]=i;
        int y=to[i];
        if(!w[i]||dep[y]^(dep[x]+1))continue;
        k=dfs(y,min(lim,w[i]));
        if(k==0)dep[y]=-1;
        w[i]-=k,w[i^1]+=k,tmp+=k,lim-=k;
    }
    return tmp;
}
int T,lim_week[75],lim_day,day,hour,rest_s,rest_e,need_cal[75][75],need_sum;
inline void clear(){
    ans=need_sum=0,cnt=1,memset(h,0,sizeof(h)),memset(now,0,sizeof(now));
}
bool meeting[75][75][75];
inline int Id_wd(int i,int j){
    return n+(i-1)*day+j;
}
inline int Id_wd_restime(int i,int j){
    return n+n*day+(i-1)*day+j;
}
inline int Id_wd_worktime(int i,int j){
    return n+2*n*day+(i-1)*day+j;
}
inline int Id_cal_dh(int i,int j){
    return n+3*n*day+(i-1)*hour+j;
}
//这四个函数就是求编号的函数
int main(){
    T=read();
    while(T--){
        clear();
        n=read(),day=read(),hour=read(),lim_day=read();
        s=0,t=n+3*n*day+day*hour+1;
        rep(i,1,n)lim_week[i]=read();
        rest_s=read(),rest_e=read();
        rep(i,1,day)rep(j,1,hour)need_cal[i][j]=read(),need_sum+=need_cal[i][j];
        rep(i,1,n)rep(j,1,day)rep(k,1,hour)meeting[i][j][k]=read(),meeting[i][j][k]^=1;
        rep(i,1,n)add(s,i,lim_week[i]);
        rep(i,1,n)rep(j,1,day){
            int x=lim_day;
            rep(k,1,hour)x-=meeting[i][j][k];
            add(i,Id_wd(i,j),x);
        } 
        rep(i,1,n)rep(j,1,day){
            int sum=rest_e-rest_s;
            rep(k,rest_s,rest_e)sum-=meeting[i][j][k];
            add(Id_wd(i,j),Id_wd_restime(i,j),sum);
            sum=hour-(rest_e-rest_s+1);
            rep(k,1,rest_s-1)sum-=meeting[i][j][k];
            rep(k,rest_e+1,hour)sum-=meeting[i][j][k];
            add(Id_wd(i,j),Id_wd_worktime(i,j),sum);
        }
        rep(i,1,n)rep(j,1,day){
            rep(k,rest_s,rest_e)if(!meeting[i][j][k])add(Id_wd_restime(i,j),Id_cal_dh(j,k),1);
            rep(k,1,rest_s-1)if(!meeting[i][j][k])add(Id_wd_worktime(i,j),Id_cal_dh(j,k),1);
            rep(k,rest_e+1,hour)if(!meeting[i][j][k])add(Id_wd_worktime(i,j),Id_cal_dh(j,k),1);
        }
        rep(i,1,day)rep(j,1,hour)add(Id_cal_dh(i,j),t,need_cal[i][j]);
        bool f=1;
        for(int i=2;i<=cnt;i+=2)if(w[i]<0){
            f=0;break;
        }
        if(!f){
            printf("No\n");
            continue;
        }
        while(bfs())ans+=dfs(s,inf);
        printf("%s\n",ans==need_sum?"Yes":"No");
    }
    return 0;
}