BZOJ 2330 [SCOI2011]糖果

题目大意

给你一堆小盆友，每个小盆友都想要糖，每个小盆友要糖的个数和别人的都有一个大小关系的限定，求发糖方法。

这道题就是差分约束，注意这是旧代码，求的是最长路，推荐使用最短路。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,k,x,a,b,cnt[1000010];
long long ans;
int to[1000010],nex[1000010],head[1000010],dis[1000010],val[1000010],tot;
bool inq[1000010];
queue<int> q;
bool spfa()
{
	memset(dis,0xef,sizeof dis);
	dis[0]=0;
	inq[0]=true;
	cnt[0]=1;
	q.push(0);
	while(!q.empty())
	{
		int tmp=q.front();
		q.pop();
		inq[tmp]=false;
		for(int i=head[tmp];i;i=nex[i])
			if(dis[to[i]]<dis[tmp]+val[i])
			{
				dis[to[i]]=dis[tmp]+val[i];
				if(!inq[to[i]])
				{
					inq[to[i]]=true;
					cnt[to[i]]++;
					if(cnt[to[i]]>=n) return false;
					q.push(to[i]);
				}
			}
	}
	return true;
}
void addedge(int tx,int ty,int tz) {to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot,val[tot]=tz;}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=n;i;--i) addedge(0,i,1);
	while(k--)
	{
		scanf("%d%d%d",&x,&a,&b);
		switch(x)
		{
			case 1:addedge(b,a,0);addedge(a,b,0);break;
			case 2:{if(a==b) {printf("-1\n");return 0;}addedge(a,b,1);break;}
            case 3:addedge(b,a,0);break;
            case 4:{if(a==b) {printf("-1\n");return 0;}addedge(b,a,1);break;}
			case 5:addedge(a,b,0);break;
		}
	}
	if(spfa())
	{
		for(int i=1;i<=n;++i) ans+=dis[i];
		printf("%lld\n",ans);
	}
	else printf("-1\n");
	return 0;
}