BZOJ 2330&Luogu 3275 糖果
幼儿园里有 N 个小朋友， lxhgww 老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候， lxhgww 需要满足小朋友们的K 个要求。幼儿园的糖果总是有限的， lxhgww 想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。
N ≤ 100000, K ≤ 100000
每个限制为三个整数： X, A, B。
-
如果 X=1，表示第 A 个小朋友分到的糖果必须和第 B 个小朋友分到的糖果一样多；
-
如果 X=2，表示第 A 个小朋友分到的糖果必须少于第 B 个小朋友分到的糖果；
-
如果 X=3，表示第 A 个小朋友分到的糖果必须不少于第 B个小朋友分到的糖果；
-
如果 X=4，表示第 A 个小朋友分到的糖果必须多于第 B 个小朋友分到的糖果；
-
如果 X=5，表示第 A 个小朋友分到的糖果必须不多于第 B个小朋友分到的糖果；
建图：
对于x=1的情况，由A向B建一条长度为0的边，并且由B向A建一条长度为0的边。
对于x=2的情况，由A向B建一条长度为1的边，表示B比A至少多一个糖果。
对于x=3的情况，由B向A建一条长度为0的边，（由糖果数少的指向多的）。
对于x=4的情况，由B向A建一条长度为1的边，表示A比B至少多一个糖果。
对于x=5的情况，由A向B建一条长度为0的边，（由糖果数少的指向多的）。
建一个超级原点0（用超级原点来限制 糖果数>=1），从超级原点向每个点连一条长度为1的边。
从超级原点出发跑==最长路，判断是否有环=>无解
判断连边顺序：考虑最长路dis[v]>=dis[u]+w；
易见每种限制都可以表示为差分约束形式的不等式。
然后这道题跑单源最长路也是很迷惑对吧√
画个图理解（李姐）一下（盗的）
你看介个图，如果跑最短路，1号点的dis=1，但显而易见，1号点的答案应该是2才是合法的，因此我们需要跑最长路，才能满足所有的约束条件。
对于情况2和情况4，如果出现了a>a或者a<a的情况，显然是无解的。
然后spfa判环，如果有一个点进入队列n-1次，就有环了？然后无解输出。
最后，记录答案的变量要记得开 long long
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int ans=0;
char last=' ',ch=getchar();
while(ch>'9'||ch<'0') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
const int mxm=300010;
const int mxn=300010;
int n,k;
int head[mxn],ecnt;
struct node{
int to,dis,nxt;
}e[mxm<<1];
void add(int from,int to,int dis){
++ecnt;
e[ecnt].to=to;
e[ecnt].dis=dis;
e[ecnt].nxt=head[from];
head[from]=ecnt;
}
queue<int> q;
bool bj,vis[mxn];
long long dis[mxn],cnt[mxn];
void spfa(int s){
q.push(s);
vis[s]=1;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
if(cnt[u]==n-1){
bj=1;
return;
}
cnt[u]++;
for(int i=head[u],v,w;i;i=e[i].nxt){
v=e[i].to;w=e[i].dis;
if(dis[v]<dis[u]+w){
dis[v]=dis[u]+w;
if(!vis[v]) {
q.push(v);
vis[v]=1;
}
}
}
}
}
long long ans;
int main(){
int x,a,b;
n=read();k=read();
for(int i=1;i<=k;i++){
x=read();a=read();b=read();
if(x==1) {
add(a,b,0);
add(b,a,0);
}
if(x==2) {
if(a==b) {
printf("-1");
return 0;
}
add(a,b,1);
}
if(x==3)
add(b,a,0);
if(x==4) {
if(a==b) {
printf("-1");
return 0;
}
add(b,a,1);
}
if(x==5)
add(a,b,0);
}
for(int i=n;i>=1;i--) add(0,i,1);
spfa(0);
if(bj){
printf("-1");
return 0;
}
for(int i=1;i<=n;i++) {
if(dis[i]==0) {
printf("-1");
return 0;
}
ans+=dis[i];
}
printf("%lld",ans);
return 0;
}