Description：

$n$ 个人，每个人都必须分到糖果，有一些限制，形如 $a=b,a>b,a\geqslant b,a<b,a\leqslant b$ ，问最少需要多少糖果。

$1\leqslant n \leqslant100000$

Solution：

按照通常差分约束的思想建图，无法处理每个人都必须分到糖果这一限制，因为 $d[i]\geqslant 1+d[0]$ 如果以 $0$ 为原点的话这是一个最长路，所以考虑按最长路的思想建图，即 $d[e[i].to]\geqslant d[k] + e[i].v$ ，然后判正环就行了。

但是这里有一个问题，就是这里求的最长路为什么是满足条件的最小解，因为在求最长路之后求出的距离一定是满足所有条件的，而且这个最长路对应从 $0$ 到这个位置的一条不等式链，这说明这个值是不能再缩小的，否则一定会有不满足，所以是最小解。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

struct edge

{

	int to,nxt,v;

}e[MAXN << 2];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

int d[MAXN];

bool v[MAXN];

bool SPFA(int k)

{

	v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(d[e[i].to] < d[k] + e[i].v)

		{

			if(v[e[i].to])return true;

			d[e[i].to] = d[k] + e[i].v;

			if(SPFA(e[i].to))return true;

		}

	}

	v[k] = false;

	return false;

}

int main()

{

	scanf("%d%d",&n,&m);

	int x,a,b;

	for(int i = n;i >= 1;--i)add(0,i,1);

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&x,&a,&b);

		if(x == 1)

		{

			add(a,b,0);

			add(b,a,0);

		}

		if(x == 2)add(a,b,1);

		if(x == 3)add(b,a,0);

		if(x == 4)add(b,a,1);

		if(x == 5)add(a,b,0);

	}

	if(SPFA(0))puts("-1");

	else

	{

		long long ans = 0;

		for(int i = 1;i <= n;++i)

		{

			ans += d[i];

		}

		cout << ans << endl;

	}

	return 0;

}