Description
幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的，lxhgww想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。
Input
输入的第一行是两个整数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个小朋友分到的糖果；
Output
输出一行，表示lxhgww老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出-1。
Sample Input
5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1
Sample Output
11
难得的一道自己想出来的题目，题解好像是差分约束与spfa的最长连。
对于A<B，A向B连一条长度为1的边；对于A≤B，A向B连一条长度为0的边；若A=B，AB互相连长度为0的边。然后，对于每个未被访问过的点，我们将其dis值设为1，并以他为起点对他跑spfa最长路(如果出现了正权环(某一点的dis值在不断更新，并且>n)，直接输出-1)。
这个算法听起来很靠谱，期望线性复杂度，但在那种坑爹的数据下被卡了，你必须将点倒着枚举。
我写了一个稳定O(n+m)的算法，其实本质和上面所讲的差不蛮多。先tarjan缩点，如果有正权环直接-1拜拜；否则topsort即可。这样就不怕被卡了。
#include<iostream>
#include<stack>
#include<queue>
#include<cstdio>
#include<cstdlib>
using namespace std; #define maxn 100010
#define maxm 200010
int cnt,side[maxn],next[maxm],toit[maxm],cost[maxm],d[maxn];
int nside[maxn],nnext[maxm],ntoit[maxm],ncost[maxm],m,tot;
int dfn[maxn],low[maxn],sum[maxn],id[maxn],arr[maxn],n;
bool vis[maxn]; stack <int> S; inline void add(int a,int b,int c)
{
next[++cnt] = side[a]; side[a] = cnt;
toit[cnt] = b; cost[cnt] = c;
} inline void ins(int a,int b,int c)
{
nnext[++cnt] = nside[a]; nside[a] = cnt;
ntoit[cnt] = b; ncost[cnt] = c; ++d[b];
} inline void dfs(int now)
{
S.push(now); dfn[now] = low[now] = ++cnt;
for (int i = side[now];i;i = next[i])
if (!vis[toit[i]])
{
if (!dfn[toit[i]]) dfs(toit[i]);
low[now] = min(low[toit[i]],low[now]);
}
if (low[now] == dfn[now])
{
++tot;
while (S.top() != now) id[S.top()] = tot,vis[S.top()] = true,S.pop();
id[S.top()] = tot,vis[S.top()] = true,S.pop();
}
} inline bool rebuild()
{
cnt = ;
for (int i = ;i <= n;++i)
for (int j = side[i];j;j = next[j])
{
if (id[toit[j]] == id[i]) sum[id[i]] += cost[j];
else ins(id[i],id[toit[j]],cost[j]);
}
for (int i = ;i <= tot;++i) if (sum[i]) return false;
return true;
} inline void topsort()
{
queue <int> team;
for (int i = ;i <= tot;++i) if (!d[i]) team.push(i),arr[i] = ;
while (!team.empty())
{
int now = team.front(); team.pop();
for (int i = nside[now];i;i = nnext[i])
{
arr[ntoit[i]] = max(arr[now]+ncost[i],arr[ntoit[i]]);
if (!--d[ntoit[i]]) team.push(ntoit[i]);
}
}
} int main()
{
freopen("2330.in","r",stdin);
freopen("2330.out","w",stdout);
scanf("%d %d",&n,&m);
for (int i = ;i <= m;++i)
{
int x,a,b; scanf("%d %d %d",&x,&a,&b);
if (x == ) add(a,b,),add(b,a,);
else if (x == ) add(a,b,);
else if (x == ) add(b,a,);
else if (x == ) add(b,a,);
else add(a,b,);
}
cnt = ; for (int i = n;i;--i) if (!dfn[i]) dfs(i);
if (!rebuild()) printf("-1"),exit();
topsort();
long long ans = ;
for (int i = ;i <= n;++i) ans += (long long)arr[id[i]];
printf("%lld",ans);
fclose(stdin); fclose(stdout);
return ;
}