题意：
幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的，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个小朋友分到的糖果；
对于所有的数据，保证 N<=100000，K<=100000，1<=X<=5，1<=A, B<=N
思路：第一反应应该是差分约束系统，但N的范围令人不放心，实际上裸SPFA也需要一些优化才能跑过去
知乎上有几位大佬说这题是tarjan缩点+拓扑排序，确实这种做法理论复杂度才是有保证的
先建立原图，对于等于关系连双向边，小于等于（和大于等于，显然等价）连单向边，先缩一次点，同一个分量里的人糖果数一定相等
再进行拓扑排序计算每一个分量的糖果数，环会导致无解，注意糖果数和前面推导不同时需要取MAX
最后特判下同一个分量里的边有没有不等的，有则无解
SPFA
var q:array[..]of longint;
head,vet,next,len,dis,time:array[..]of longint;
inq:array[..]of boolean;
n,m,i,x,a,b,tot:longint;
ans,tmp:int64; procedure add(a,b,c:longint);
begin
inc(tot);
next[tot]:=head[a];
vet[tot]:=b;
len[tot]:=c;
head[a]:=tot;
end; procedure spfa;
var t,w,i,u,e,v:longint;
begin
fillchar(time,sizeof(time),);
t:=; w:=-;
for i:= to n do
begin
dis[i]:=; inc(w); q[w]:=i; inq[i]:=true;
end; while t<=w do
begin
u:=q[t mod n]; inc(t); inq[u]:=false;
e:=head[u];
while e<> do
begin
v:=vet[e];
if dis[u]+len[e]>dis[v] then
begin
dis[v]:=dis[u]+len[e];
if not inq[v] then
begin
inc(time[v]);
if time[v]>n then
begin
writeln(-); ans:=-;
exit;
end;
inc(w); q[w mod n]:=v; inq[v]:=true;
end;
end;
e:=next[e];
end;
end;
end; begin read(n,m);
for i:= to m do
begin
read(x,a,b);
if (x and =)and(a=b) then
begin
writeln(-);
exit;
end;
case x of
:begin add(b,a,); add(a,b,); end;
:add(a,b,);
:add(b,a,);
:add(b,a,);
:add(a,b,);
end;
end;
spfa;
if ans= then
begin
for i:= to n do ans:=ans+dis[i]; writeln(ans);
end; end.
tarjan+拓扑排序
#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int M=;
int head[M],vet[M],next[M],len[M],a[M],b[M],c[M],dfn[M],low[M],flag[M],ind[M],stack[M],s[M];
int n,m,i,tot,id,top,cnt;
long long d[M],size[M]; void add(int a,int b,int c)
{
next[++tot]=head[a];
vet[tot]=b;
len[tot]=c;
head[a]=tot;
ind[b]++;
} void swap(int &a,int &b)
{
int t;
t=a;a=b;b=t;
} void dfs(int u)
{
int e,v;
flag[u]=;
stack[++top]=u;
dfn[u]=low[u]=++cnt;
for(e=head[u];e;e=next[e])
{
v=vet[e];
if(!flag[v])
{
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(!s[v]) low[u]=min(low[u],low[v]);
}
if(low[u]==dfn[u])
{
id++;
while(stack[top]!=u)
{
s[stack[top]]=id;
size[id]++;
top--;
}
s[stack[top]]=id;
size[id]++;
top--;
} } long long solve()
{
queue<int> q;
int num;
long long sum;
for(int i=;i<=id;i++)
if(!ind[i])
{
q.push(i);
d[i]=;
}
if(q.empty()) return -;
num=;
while(!q.empty())
{
int u=q.front(); q.pop(); num++;
for(int e=head[u];e;e=next[e])
{
int v=vet[e];
ind[v]--;
d[v]=max(d[v],d[u]+len[e]);
if(!ind[v]) q.push(v);
}
}
if(num<id) return -;
else
{
sum=;
for(int i=;i<=id;i++) sum=sum+d[i]*size[i];
return sum;
} } int main()
{
// freopen("bzoj2330.in","r",stdin);
// freopen("bzoj2330.out","w",stdout);
scanf("%d%d",&n,&m);
id=;
for(i=;i<=m;i++)
{
scanf("%d%d%d",&a[i],&b[i],&c[i]);
if(a[i]==||a[i]==) swap(b[i],c[i]);
if(a[i]==)
{
add(b[i],c[i],);
add(c[i],b[i],);
}
if(a[i]==||a[i]==) add(b[i],c[i],);
}
for(i=;i<=n;i++)
if(!flag[i]) dfs(i);
//printf("%d\n",id);
memset(head,,sizeof(head));
memset(ind,,sizeof(ind));
tot=;
for(i=;i<=m;i++)
if(s[b[i]]!=s[c[i]])
{
if(a[i]==||a[i]==) add(s[b[i]],s[c[i]],);
else add(s[b[i]],s[c[i]],);
}
else
{
if(a[i]==||a[i]==)
{
printf("-1\n");
return ;
}
}
printf("%lld\n",solve());
return ;
}