「题解」糖果

幼儿园里有 $N$ 个小朋友，$\text{lxhgww}$ 老师现在想要给这些小朋友们分配糖果……

一 题目

原题链接

描述

幼儿园里有 $N$ 个小朋友，$\text{lxhgww}$ 老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，$\text{lxhgww}$ 需要满足小朋友们的 $K$ 个要求。幼儿园的糖果总是有限的，$\text{lxhgww}$ 想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求

输入

输入的第一行是两个整数 $N$，$K$。接下来 $K$ 行，表示这些点需要满足的关系，每行 $3$ 个数字，$X$，$A$，$B$。如果 $X=1$， 表示第 $A$ 个小朋友分到的糖果必须和第 $B$ 个小朋友分到的糖果一样多；如果 $X=2$， 表示第 $A$ 个小朋友分到的糖果必须少于第 $B$ 个小朋友分到的糖果；如果 $X=3$， 表示第 $A$ 个小朋友分到的糖果必须不少于第 $B$ 个小朋友分到的糖果；如果 $X=4$， 表示第 $A$ 个小朋友分到的糖果必须多于第 $B$ 个小朋友分到的糖果；如果 $X=5$， 表示第 $A$ 个小朋友分到的糖果必须不多于第 $B$ 个小朋友分到的糖果。

输出

输出一行，表示 $\text{lxhgww}$ 老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出 $-1$。

---

二 题解

本题的差分约束实现需要变一下，但不着急，先分析给出的条件。

罗列如下：

编号	条件	变换
1	$x_a=x_b$	$x_a-x_b \leqslant 0,x_b-x_a \leqslant 0$
2	$x_a-x_b < 0$	$x_a-x_b \leqslant -1$
3	$x_a-x_b \geqslant 0$	$x_b-x_a \leqslant 0$
4	$x_a-x_b > 0$	$x_b-x_a \leqslant -1$
5	$x_a-x_b \leqslant 0$	\

在使用最短路求解差分约束的时候，不难发现影响系统的解（单源最短路）的只有图上的负权边。

对于本题，因为边权仅存在$0$或$-1$两种情况，故所求的最短路长度一定为负数或零。
对于负数，原来的不等关系会不成立（它们仅针对正数），从而使求解出现一些偏差。也就是说，我们求出的解实际上是不等式解的相反数。进一步来讲，对于所有的$d_i$，满足$ -d_a - (-d_b) \leqslant C$，与题目中推出的三角形不等式恰好相反！
那直接这样建边一定是不行的。我们需要把题目中的条件乘上一个$-1$，这样我们求解最短路之后，$x_i=-d_i$才会是答案。

如下：

编号	原不等式	新不等式	对应连边
1	$x_a-x_b \leqslant 0,x_b-x_a \leqslant 0$	同前	$ \text{add(a,b,0) ;add(b,a,0)}$
2	$x_a-x_b \leqslant -1$	$x_b-x_a \leqslant -1$	$ \text{add(a,b,-1)}$
3	$x_b-x_a \leqslant 0$	$x_a-x_b \leqslant 0$	$ \text{add(b,a,0)}$
4	$x_b-x_a \leqslant -1$	$x_a-x_b \leqslant -1$	$ \text{add(b,a,-1)}$
5	$x_a-x_b \leqslant 0$	$x_b-x_a \leqslant 0$	$ \text{add(a,b,0)}$

另，每个小朋友至少有一个糖果，所以最短路径长度需要初始为$-1$。

还有一个坑点（毒瘤），测试点#6是一个很长的链，所以在新建原点时，必须倒序连边，防止每次都会走链然后被卡TLE。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
using namespace std;

#define LL long long

const int CP=1e5+5;
const int CE=CP*1008;

const LL INF=0x7f7f7f7f7f7f3f3f;

class fs{
  public:
    int to,nxt;
    LL dist;
    void init(int t,int n,LL d){
        to=t; nxt=n; dist=d;
    }
}E[CE];
int hd[CP],ecnt=0;
void add(int x,int y,LL z){
    E[++ecnt].init(y,hd[x],z);
    hd[x]=ecnt;
}

int n,m;

//spfa
LL d[CP];
int times[CP];
bool ins[CP];

bool spfa(int s)
{
    memset(d,0x3f,sizeof(d));
    memset(ins,false,sizeof(ins));
    memset(times,0,sizeof(times));
    d[s]=0;
    
    queue<int>Q;
    Q.push(s);
    
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        ins[u]=false;
        
        for(int k=hd[u]; k; k=E[k].nxt)
        {
            fs e=E[k];
            if(d[e.to] > d[u]+e.dist) //最短路
            {
                d[e.to] = d[u]+e.dist;
                if(!ins[e.to])
                {
                    Q.push(e.to);
                    ins[e.to]=true;
                    if(++times[e.to] == n) //判负环
                        return false;
                }
            }
        }
    }
    
    return true;
}

int main()
{
    bool flag=false;
    
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int x,a,b;
        scanf("%d%d%d",&x,&a,&b);
        
        if(x==1){
            add(a,b,0); add(b,a,0);
        }
        if(x==2){ //出现负自环边直接退出
            if(a == b){
                flag=true;
                break;
            }
            add(a,b,-1);   
        }
        if(x==3)
            add(b,a,0);
        if(x==4){
            if(a == b){
                flag=true;
                break;
            }
            add(b,a,-1);
        }
        if(x==5) 
            add(a,b,0);
    }
    
    for(int i=n; i; i--) //新建总源（必须倒序循环）
        add(0,i,-1); //这里相当于初始最短路径长度
    
    if(spfa(0) && !flag)
    {
        LL sum=0;
        for(int i=1;i<=n;i++)
            sum+=d[i];
        printf("%lld",-sum); //对sum取相反数
    }
    else 
        printf("-1");
        
    return 0;
}