算法提高课汇总

模型抽象

小朋友的要求可以用不等式表示, 求不等式组的最值解即差分约束问题.

求最小值 --> 最长路算法. 先将原题的不等式等价变形为$\ge$的形式.

1. $A$和$B$一样多: $A = B$ --> $A\ge B+0, B\ge A+0$

2. $A$少于$B$: $A\lt B$ --> $B\ge A + 1$

3. $A$不少于$B$: $A\ge B$ --> $A\ge B+0$

4. $A$多于$B$: $A\gt B$ --> $A\ge B + 1$

5. $A$不多于$B$: $A\le B$ --> $B\ge A+0$

最小值问题必须存在变量有明确下界: 每个小朋友都要分到糖果, 即$dist[u]\ge 1$. 可以创建一个虚拟源点$s$
指向所有顶点, $dist[s] = 0$, 边权均为$1$.

注意判断源点限制: 从源点出发要经过所有边. 由于$s$与所有点相连, 所以从$s$出发必然经过所有边, 满足条件.

代码实现 $spfa$

• $spfa$判断负环会超时, 参考 AcWing 1165. 单词环 , 可以通过将$spfa$数组修改为栈优化运行时间.

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

typedef long long ll; 

const int N = 1e5 + 10, M = 1e5 * 3 + 10;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
ll dist[N]; int q[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 ++;
}

bool spfa()
{
    memset(dist, -0x3f, sizeof dist); //求最长路
    dist[0] = 0; //源点
    int tt = 0;
    q[tt ++] = 0;  

    while( tt )
    {
        int u = q[-- tt]; //栈结构

        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] >= n + 1 )   return true; //顶点个数要包括虚拟源点

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

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    while( m -- )
    {
        int x, a, b;
        scanf("%d%d%d", &x, &a, &b);
        switch( x )
        {
            case 1: add(a, b, 0), add(b, a, 0); break;
            case 2: add(a, b, 1); break;
            case 3: add(b, a, 0); break;
            case 4: add(b, a, 1); break;
            case 5: add(a, b, 0); break;
        }
    }
    for( int i = 1; i <= n; i ++ )  add(0, i, 1); //源点设为0; 0-->i 边权为1 明确下界

    if( spfa() )    puts("-1");
    else
    {
        ll res = 0;
        for( int i = 1; i <= n; i ++ )  res += dist[i];
        printf("%lld\n", res);
    }

    return 0;
}