题目链接:https://ac.nowcoder.com/acm/contest/5278/L

思路

这题是要求最小天数,我们不妨先转换一下思路:如果在天数固定并且已知的情况下,能不能保证所有物品都能被得到?这个问题显然可以用最大流来解决。建图,满足以下三点:

  1. 周一到周日抽象成7个点,(自己构造出来的)源点依次与它们连边,容量为经过这天的次数
  2. 把每天与这天可以获得的所有物品连边,容量无限
  3. 把所有物品依次与(自己构造出来的)汇点连边,容量为每个物品需要得到的次数

对这个图跑一遍最大流得到maxflow,假设所有物品需要得到的次数为sum,只要maxflow=sum,那么这个天数就能保证所有物品都能被得到。

现在,问题是要尽量最小化这个天数,怎么办?可以二分 (能二分就千万别暴力,否则TLE等着你)

二分天数,对于每个固定的天数都用judge函数判断,也就是跑一遍最大流,看看在这个天数下能不能得到所有物品。如果能,减小天数;不能,则增大天数。注意每个judge函数里面都要重新建图,然后跑一遍最大流,所以先把要连的所有边都用数组记下来。

最后,注意一下二分的上下界问题,这个问题很重要。 所谓二分的上下界,其实就是所有可能答案的最小值和最大值。

最好情况,最小天数当然是1,二分下界就是1; 最坏情况呢?每天最多能取E次,所有物品都要被取1e5次,一共1000个物品,而且所有物品每周都只能在周一得到,这样就是最坏情况。算一下:1e5*1000/E=1e8/E就是最少需要经过周一的次数,然后为了经过周一,需要7天才能经过一次,那么总共需要1e8/E7天,二分上界是7e8/E。*

为什么要这么费心思的求出准确的上界?我把上界写成0x7f7f7f7f(2e9左右)再去二分不行吗?可以,但是在跑最大流的时候会爆int,这个错误不易察觉,而且会多进入几次judge函数,也就会多跑几次最大流,浪费时间。最小天数上界是7e8/E,这样就保证了在建图的第一点,也就是源点与7个点连边的容量之和小于int(最大是day÷7*E=7e8/E÷7*E=1e8),“水源流量”小于int,那跑最大流的时候无论如何也无法超过int了。

当然你把所有与流量有关的变量都写成long long也能AC,也可以不想这么多。我想这些是考虑到上界的问题,上界最好不要随便搞个inf=2e9上去,二分的时候可能会出错。

这题确实得花点心思好好想想。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+20,M=1e5+10,inf=0x7f7f7f7f;
int n,E,s,t,cnt,tot,sum,head[N+10],dep[N+10],c[N+10],cur[N+10];
struct edge
{
    int to,w,next;
}e[M<<1];
struct node
{
    int x,y,z;
}p[N*N];
void add(int x,int y,int z)
{
    e[cnt].to=y;
    e[cnt].w=z;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
void add_edge(int x,int y,int z)
{
    add(x,y,z);
    add(y,x,0);//反向边初始为0
}
bool bfs()
{
    queue<int>q;
    memset(dep,0,sizeof(dep));
    q.push(s);
    dep[s]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            int v=e[i].to;
            if(e[i].w>0&&dep[v]==0)
            {
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    if(dep[t])return 1;
    return 0;
}
int dfs(int u,int flow)
{
    if(u==t)return flow;//到达汇点,返回这条增广路上的最小流量
    for(int& i=cur[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        if(e[i].w>0&&dep[v]==dep[u]+1)
        {
            int di=dfs(v,min(flow,e[i].w));//min(flow,e[i].w)表示起点到v的最小流量
            if(di>0)//防止dfs结果return 0的情况,如果di=0会死循环
            {
                e[i].w-=di;
                e[i^1].w+=di;//反向边加上di
                return di;//di表示整条增广路上的最小流量,回溯的时候一直向上返回,返回的di是不变的
            }
        }
    }
    return 0;//找不到增广路,到不了汇点
}
int dinic()
{
    int ans=0;
    while(bfs())
    {
        memcpy(cur,head,sizeof(head));
        while(int d=dfs(s,inf))
            ans+=d;
    }
    return ans;
}
bool judge(int day)
{
    cnt=0;
    memset(head,-1,sizeof(head));
    s=0,t=n+7+1;
    int k=day/7,rest=day%7;
    for(int i=1;i<=n;i++)
        add_edge(i,t,c[i]);
    for(int i=1;i<=tot;i++)
        add_edge(p[i].x,p[i].y,p[i].z);
    for(int i=1;i<=7;i++)
        add_edge(s,i+n,k*E+(i<=rest?E:0));
    //这个i<=rest?E:0,很简洁
    //若rest=0,则不会多出天数,直接加0
    //若rest=1~6,则多出的这些天数对应能取得物品的次数都要+E
    int maxflow=dinic();
    return maxflow==sum;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>E;
    int m,x;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
        sum+=c[i];
        cin>>m;
        while(m--)
        {
            cin>>x;
            p[++tot]={x+n,i,inf};//暂时存边
        }
    }
    int l=1;
    int r=7e8/E;//r=inf会错,除非把所有与流量相关的变量都写成long long
    int ans;
    while(l<=r)
    {
        int mid=l+(r-l)/2;
        if(judge(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}
/*
5 1
2 4 1 3 5 7
2 3 2 4 6
2 2 1 2
2 2 3 4
2 2 5 6

ans:10
*/