糖果
【题目描述】
幼儿园里有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个小朋友分到的糖果；
【输出格式】
输出一行，表示lxhgww老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出-1。
【样例输入】
5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1
【样例输出】
11
【数据范围】
对于30%的数据，保证 N<=100
对于100%的数据，保证 N<=100000
对于所有的数据，保证 K<=100000，1<=X<=5，1<=A, B<=N
题解：
对于题目要求的五种情况连边：
1、如果A和B一样多 —> (A, B, 0) 和 (B, A, 0)
2、如果A小于B —> (A, B, 1)
3、如果A不小于B —> (B, A, 0)
4、如果A大于B —> (B, A, 1)
5、如果A不大于B —> (A, B, 0)
无解：
1、要求某一人的糖果数大于或小于自己的 （有一条本身到本身长度不为0的边)
2、环 (一个点被访问超过n次)
附：此题超过int范围
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
inline int Get()
{
int x = ;
char c = getchar();
while('' > c || c > '') c = getchar();
while('' <= c && c <= '')
{
x = (x << ) + (x << ) + c - '';
c = getchar();
}
return x;
}
const int me = ;
int tot;
int nex[me], fir[me], to[me], va[me];
int t, w, n, k;
long long ans;
int s[me];
int ue[me];
int len[me];
bool vis[me];
bool Same(int x, int y)
{
if(x == y)
{
printf("-1");
exit();
}
}
inline void Ins(int x, int y, int z)
{
nex[++tot] = fir[x];
fir[x] = tot;
to[tot] = y;
va[tot] = z;
}
inline bool Spfa()
{
while(t < w)
{
int u = ue[++t];
for(int i = fir[u]; i; i = nex[i])
{
int v = to[i];
if(len[v] < len[u] + va[i])
{
++s[v];
if(s[v] >= n) return false;
len[v] = len[u] + va[i];
if(!vis[v])
{
vis[v] = true;
ue[++w] = v;
}
}
vis[u] = false;
}
}
return true;
}
int main()
{
n = Get(), k = Get();
for(int i = ; i <= k; ++i)
{
int flag = Get();
int x = Get();
int y = Get();
if(flag == ) Ins(x, y, ), Ins(y, x, );
if(flag == ) Ins(x, y, ), Same(x, y);
if(flag == ) Ins(y, x, );
if(flag == ) Ins(y, x, ), Same(x, y);
if(flag == ) Ins(x, y, );
}
for(int i = ; i <= n; ++i)
{
ue[++w] = i;
len[i] = ;
vis[i] = true;
}
if(!Spfa())
{
printf("-1");
return ;
}
for(int i = ; i <= n; ++i)
ans += len[i];
printf("%lld", ans);
}