算法：差分约束

题目中求糖果总数的最小值，即每个小朋友分到糖果的最小值

所以是求图中到每个点的最长路，不等式为：$dis_j >= dis_t +len$,边为：t->j

当 x = 1 时，$x_A=x_B$ 变为 $ x_A > =x_B $ && $ x_A <= x_B $
当 x = 2 时，$x_A < x_B$ 变为 $ x_B >= x_A+1 $
当 x = 3 时，$x_A >= x_B$ 变为 $ x_A > =x_B+0 $
当 x = 4 时，$x_A > x_B$ 变为 $ x_A >= x_B+1 $
当 x = 5 时，$x_A <= x_B$ 变为 $ x_B >= x_A+0 $

注：从小于或大于通过+1变为大于等于或小于等于，只有整型变量才可以

SPFA求判断负环时，用栈来代替队列，因为在一些特殊情况下栈更快：

把刚入栈的点立刻弹出，可以优先检查这个点接下来的路径，很多情况下能更快找到负环

这种方法类似广搜变为深搜，但用栈的遍历顺序不完全是dfs序

#include <bits/stdc++.h>
using namespace std;
int n,m,idx,sum[100010];
long long dis[100010],ans;
bool vis[100010];
int to[300010],len[300010],nex[300010],head[300010];
void add(int a,int b,int c)
{
    to[idx]=b;
    len[idx]=c;
    nex[idx]=head[a];
    head[a]=idx++;
}//此题在时间上卡了用vector存边，恰好最后一个点TLE
bool spfa(int start)
{
    memset(dis,-0x3f,sizeof(dis));
    dis[start]=0;
    stack<int> q;
    q.push(start);
    vis[start]=true;
    while(!q.empty())
    {
        int t=q.top();
        q.pop();
        vis[t]=false;
        for(int i=head[t];i!=-1;i=nex[i])
            if(dis[to[i]]<dis[t]+len[i])
            {
                dis[to[i]]=dis[t]+len[i];
                sum[to[i]]=sum[t]+1;
                if(sum[to[i]]>n) return true;
                if(!vis[to[i]])
                {
                    q.push(to[i]);
                    vis[to[i]]=true;
                }
            }
    }
    return false;
}
int main()
{
    scanf("%d %d",&n,&m);
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++)
    {
        int op,a,b;
        scanf("%d %d %d",&op,&a,&b);
        if(op==1)
        {
            add(a,b,0);
            add(b,a,0);
        }
        else if(op==2) add(a,b,1);
        else if(op==3) add(b,a,0);
        else if(op==4) add(b,a,1);
        else add(a,b,0);
    }
    for(int i=1;i<=n;i++) add(0,i,1);
    if(spfa(0)) puts("-1");
    else
    {
        for(int i=1;i<=n;i++) ans+=dis[i];
        printf("%lld",ans);//最后最大的结果可能是n^2,所以用long long
    }
    return 0;
}

2021年11月7日15:43:37