【题目描述】 幼儿园里有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 【题解】 我们令第i个孩子分到的糖果个数为m[i]，我们可以得出这几个不等式： x==1:m[a]-m[b]=0==>m[a]-m[b]>=0&&m[b]-m[a]<=0; x==2:m[b]-m[a]>0==>m[b]-m[a]>=1; x==3:m[a]-m[b]>=0; x==4:m[a]-m[b]>0==>m[a]-m[b]>=1; x==5:m[b]-m[a]>=0; 根据这6个不等式建图，在把每个点（1-n）跟0这个点连接起来，跑一边最长路就可以了。 那么什么情况输出-1呢？一是x==2,4时a==b的情况，二是负环，三是没有最长路这个解法的情况。 代码如下：
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=100000; int head[N+5],num; int dis[N+5],flag[N+5],mark[N+5]; queue<int> q; int n,k; long long ans=0; struct edge { int u,v,w; int next; edge(){next=-1;} }ed[4*N+5]; void build(int u,int v,int w) { ed[++num].v=v; ed[num].w=w; ed[num].next=head[u]; head[u]=num; } bool SPFA() { q.push(0); flag[0]=1,mark[0]=1,dis[0]=0; while(!q.empty()) { int u=q.front();q.pop(); flag[u]=0; for(int i=head[u];i!=-1;i=ed[i].next) { int v=ed[i].v; if(dis[v]<dis[u]+ed[i].w)//最长路 { dis[v]=dis[u]+ed[i].w; if(!flag[v]) { flag[v]=1; q.push(v); if(++mark[v]>=n)return false;//判负环 } } } } return true; } int main() { memset(head,-1,sizeof(head)); scanf("%d%d",&n,&k); while(k--) { int x,a,b; scanf("%d%d%d",&x,&a,&b); if(x==1) {build(a,b,0);build(b,a,0);}//m[a]-m[b]=0; if(x==2) { if(a==b){printf("-1\n");return 0;} build(a,b,1);//m[b]-m[a]>=1; } if(x==3)build(b,a,0);//m[a]-m[b]>=0; if(x==4) { if(a==b){printf("-1\n");return 0;} build(b,a,1);//m[a]-m[b]>=1; } if(x==5)build(a,b,0);//m[b]-m[a]>=0; } for(int i=n;i>0;i--)build(0,i,1); if(!SPFA()){printf("-1\n");return 0;} for(int i=1;i<=n;i++)ans+=(long long)dis[i]; printf("%lld\n",ans); return 0; }