洛谷P3275 [SCOI2011]糖果 题解

题目链接：

https://www.luogu.org/problemnew/show/P3275

分析：

本题就是一个裸的差分约束。

---

核心：

$x=1$时，$a=b,a->b,b->a$，连边权值为$0$

$x=2$时，$a<b$,此时我们用整数这个性质，于是可知$a\le b-1$,$a->b$,权值为$1$

$x=3$时，$b\le a$,$b$向$a$连权值为$0$

$x=4$时，$b<a$,此时我们用整数这个性质，于是可知$b\le a-1$,$b->a$,权值为$1$

$x=5$时，$a\le b$,$a$向$b$连权值为$0$

---

然后就是因为每个人都有糖，所以$0$向$i$连边，权值为$1(1\le i<=n)$

这里很多的存储方式为了避免链的超时，需要倒序，但是这里的vector邻接表存储倒序反而超时！

---

提醒：

$x=2$或$x=4$时，可能出现$A=B$的情况，此时要特判输$-1$

数据较大，要开$long$ $long$

代码：

#include<cstdio>
#include<vector>
#include<queue> 
using namespace std;
struct edge
{
	int to,val;
	edge(int _to,int _val)
	{
		to=_to;
		val=_val; 
	}
};
long long dis[300005];
int vis[300005],tot[300005];
vector<edge>e[300005];
void add(int x,int y,int w)
{
	e[x].push_back(edge(y,w));
}
int main()
{
	queue<int>q;
	int n,k,X,A,B;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;i++)
	{
		scanf("%d%d%d",&X,&A,&B);
		if(X==1)
		{
			add(A,B,0);
			add(B,A,0);
		}
		else
		if(X==2)
		{
			if(A==B)
			{
				printf("-1\n");
				return 0;
			}
			add(A,B,1);
		}
		else
		if(X==3)
		{
			add(B,A,0);
		}
		else
		if(X==4)
		{
			if(A==B)
			{
				printf("-1\n");
				return 0;
			}
			add(B,A,1);
		}
		else
		add(A,B,0);
	}
	for(int i=1;i<=n;i++)
	{
		add(0,i,1);
	}
	vis[0]=1;
	q.push(0);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		vis[x]=0;
		for(int i=0;i<e[x].size();i++)
		{
			int y=e[x][i].to;
			if(dis[y]<dis[x]+e[x][i].val)
			{
				dis[y]=dis[x]+e[x][i].val;
				if(vis[y]==0)
				{
					vis[y]=1;
					q.push(y);
					tot[y]++;
					if(tot[y]>n)
					{
						printf("-1\n");
						return 0;
					}
					
				}
			}
		}
	}
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		ans+=dis[i];
	}
	printf("%lld\n",ans);
	return 0;
}