[SCOI2011]糖果

65 阅读 0 评论 43 点赞

我是靠谱客的博主危机鞋垫，最近开发中收集的这篇文章主要介绍[SCOI2011]糖果，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

 
 [SCOI2011]糖果 

 
 题目描述 

 
 幼儿园里有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。 

 
 输入输出样例 

 
 输入样例#1： 

 
 5 71 1 22 3 24 4 13 4 55 4 52 3 54 5 1 

 
 输出样例#1： 

11

 
 说明 

 
 【数据范围】 

 
 对于30%的数据，保证 N<=100 

 
 对于100%的数据，保证 N<=100000 

 
 对于所有的数据，保证 K<=100000，1<=X<=5，1<=A, B<=N 

 
 题解： 

 
 差分约束题目，1操作看出a-b>=0 &&b-a>=0，所以a和b互相连一条权值为0的边。 

 
 2操作看成b-a>=1从a向b连一条长度为1的边，3看成a-b>=1，4看成a-b>=1，5看成b-a>=0求最长路。 

 
 代码： 

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const LL max_n = 100001;
const LL inf = 1e9+7;

LL point[max_n],nxt[max_n<<1],v[max_n<<1],w[max_n<<1];
LL dis[max_n];
bool vis[max_n];
queue<LL> q;
LL n,k,x,y,c,tot,ans;

inline void init()
{
	memset(point,-1,sizeof(point));
	memset(nxt,-1,sizeof(nxt));
	tot=-1;
}

inline void addedge(LL x,LL y,LL val)
{
	++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; w[tot]=val;
}

inline bool spfa()
{
	while(!q.empty())
	{
		LL now=q.front(); q.pop();
		if(dis[now]>n) return true;
		for(LL i=point[now]; i!=-1; i=nxt[i])
		  if(dis[now]+w[i]>dis[v[i]])
		  {
		  	dis[v[i]]=dis[now]+w[i];
		  	if(!vis[v[i]]) q.push(v[i]);
		  	vis[v[i]]=true;
		  }
		vis[now]=false;
	}
	return false;
}

int main()
{
	scanf("%lld%lld",&n,&k);
	init();
	for(LL i=1; i<=k; ++i)
	{
		scanf("%lld%lld%lld",&c,&x,&y);
		if(c==1) addedge(x,y,0),addedge(y,x,0);
		else if(c==2) addedge(x,y,1);
		else if(c==3) addedge(y,x,0);
		else if(c==4) addedge(y,x,1);
		else addedge(x,y,0);
		if((c==2 || c==4) && x==y)
		{
			printf("-1n");
			return 0;
		}
	}
	for(LL i=1; i<=n; ++i)
	{
		q.push(i);
		dis[i]=1;
		vis[i]=true;
	}
	if(spfa())
	{
		printf("-1n");
		return 0;
	}
	for(LL i=1; i<=n; ++i)
	  ans+=dis[i];
	printf("%lldn",ans);
	return 0;
}