算法提高课汇总

理解题意

• $R(i): [i, i+1)$ 小时超市至少需要收营员的数量.

• $num(i): [i, i + 8)$ 从$i$小时开始工作$8$小时的申请人数量. 注意可能会连续工作至第二天.

差分约束

设$x(i):$ 从$num(i)$申请人中实际选择的数量, 建立不等式关系:

• $0\le x(i)\le num(i)$

• $x_{i-7} + x_{i-6} + … + x_i\ge R(i)$: 在$[i, i + 1)$时段收营员的数量 $\ge R(i)$.

不等式关系包含超过两个变量, 由于是区间和, 考虑使用前缀和思路.

• $s_i = x_1 + x_2 + … + x_i, 1\le i\le 24$.

• $s_0 = 0$. 符合定义, 且可以作为最小值下界.

为方便计算, 对所有时段加上偏移量1, 且注意特殊处理工作至第二天的情况. 题目求最小值, 建立$\ge$关系:

• $0\le x(i)$ --> $s_i - s_{i-1}\ge 0$ --> $s_i\ge s_{i-1} + 0$

• $x(i)\le num(i)$ --> $s_i - s_{i-1}\le num(i)$ --> $s_{i-1}\ge s_i - num(i)$

• $8\le i\le 24: s_i - s_{i-8}\ge R(i)$ --> $s_i\ge s_{i-8} + R(i)$

• $1\le i\le 7: s_i - s_0 + s_{24} - s_{i + 16}\ge R(i)$ --> $s_i\ge s_{i + 16} - s_{24} + R(i)$

其中最后一个不等式包含$3$个变量, 因为题目规模较小, 我们可以枚举$s_{24}$的所有可能: $[0, 1000]$,
因为题目求解的是$s_{24}$的最小值, 从小到大枚举$s_{24}$的所有可能值, 在第一个使得原题有解的
地方停止; 若所有可能值均无解, 则原题无解.

代码实现

• 源点: 考虑不等式$s_i\ge s_{i-1} + 0$, 图中存在$i - 1\rightarrow i$的边, 从$0$开始可以遍历所有顶点,
  可以遍历所有边.

• $s_{24} = c$: 为满足每次$s_{24}$为定值, 我们需要额外建立不等式. 由于$s_0 = 0, s_{24} = c$,
  可建立不等式$s_0 + c\le s_{24}\le s_0 + c$ --> $s_{24}\ge s_0 + c, s_0\ge s_{24} - c$.

  源点$s_0$不需要用不等式限制, 因为在最长路算法中可以直接初始化其值, 且对无环图保证其值不会
  再被更新.而$s_{24}$不能直接初始化, 因为后续可能被其他点更新, 需要额外建立不等式即建立额外的
  有向边以保证其为常量.

#include <cstring>
#include <iostream>

using namespace std;

const int N = 30, M = 80;

int n;
int r[N], num[N];
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[N]; bool st[N];
int cnt[N];

void add(int u, int v, int c)
{
    e[idx] = v, w[idx] = c, ne[idx] = h[u], h[u] = idx ++;
}

void build(int c)
{//s(24) = c 建图
    memset(h, -1, sizeof h);
    idx = 0;
    for( int i = 1; i <= 24; i ++ )
    {
        add(i - 1, i, 0); //si >= s(i - 1) + 0
        add(i, i - 1, -num[i]); //s(i - 1) >= si - num(i)
        if( i <= 7 )    add(i + 16, i, -c + r[i]); //si >= s(i + 16) - s(24) + r(i)
        else    add(i - 8, i, r[i]); //si >= s(i - 8) + r(i)
    }
    add(0, 24, c); add(24, 0, -c); //s0 + c <= s(24) <= s0 + c
}

bool spfa(int c)
{
    build(c);

    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);
    memset(dist, -0x3f, sizeof dist);
    int hh = 0, tt = 0;
    q[tt ++] = 0; dist[0] = 0; st[0] = true;

    while( hh != tt )
    {
        int u = q[hh ++];
        if( hh == N )   hh = 0;

        st[u] = false;

        for( int i = h[u]; ~i; i = ne[i] )
        {
            int v = e[i];
            if( dist[v] < dist[u] + w[i] )
            {
                dist[v] = dist[u] + w[i];
                cnt[v] = cnt[u] + 1;

                if( cnt[v] >= 25 )  return true;

                if( !st[v] )
                {
                    st[v] = true;
                    q[tt ++] = v;
                    if( tt == N )   tt = 0;
                }
            }
        }
    }
    return false;
}

int main()
{
    int T;
    cin >> T;
    while( T -- )
    {
        for( int i = 1; i <= 24; i ++ ) cin >> r[i];
        memset(num, 0, sizeof num);
        cin >> n;
        for( int i = 0; i < n; i ++ )
        {
            int t;
            cin >> t;
            num[t + 1] ++;
        }

        bool flag = false; //是否有解
        for( int i = 0; i <= 1000; i ++ )
            if( !spfa(i) ) //无环 -> 有解
            {
                cout << i << endl;
                flag = true;
                break;
            }
        if( !flag ) puts("No Solution");
    }
    return 0;
}