背景：

数学竞赛二等，基本卡线，差$5+pts$一等（按照$WJ$的说法，过程怒扣$20+pts$），惨…
（之前的看错题是假的）

题目传送门：

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

题意：

一些人，他们的权值满足一些关系，求权值和的最小值。

思路：

差分约束裸题。
但是有些坑，不知道为什么正常建边用$spfa$会超时（$90pts$），发现题解中的逆向建边才不会超时，太假啦。

代码：

#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<algorithm>
#define LL long long
using namespace std;
queue<int> f;
	struct node{int x,y,z,next;} a[800010];
	int last[400010],tot[400010];
	LL dis[400010];
	bool bz[400010];
	int n,m,st,len=0;
	LL ans=0;
void ins(int x,int y,int z)
{
	a[++len]=(node){x,y,z,last[x]}; last[x]=len;
}
bool spfa()
{
	dis[st]=0;
	memset(bz,true,sizeof(bz));
	bz[st]=false;
	f.push(st);
	while(!f.empty())
	{
		int x=f.front();
		f.pop();
		for(int i=last[x];i!=-1;i=a[i].next)
		{
			int y=a[i].y;
			if(dis[x]+a[i].z>dis[y])
			{
				dis[y]=dis[x]+a[i].z;
				if(bz[y])
				{
					if(++tot[y]==n) return false;
					f.push(y),bz[y]=false;
				}
			}
		}
		bz[x]=true;
	}
	return true;
}
void check(int x,int y)
{
	if(x==y)
	{
		printf("-1");
		exit(0);
	}
}
int main()
{
	int t,x,y;
	scanf("%d %d",&n,&m);
	st=0;
	memset(last,-1,sizeof(last));
	for(int i=n;i>=1;i--)
		ins(st,i,1);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d",&t,&x,&y);
		switch(t)
		{
			case 1:ins(x,y,0),ins(y,x,0);break;
			case 2:check(x,y);ins(x,y,1);break;
			case 3:ins(y,x,0);break;
			case 4:check(x,y);ins(y,x,1);break;
			case 5:ins(x,y,0);break;
		}
	}
	if(!spfa()) {printf("-1");return 0;}
	for(int i=1;i<=n;i++)
		ans+=dis[i];
	printf("%lld",ans);
}

最后

以上就是英俊板凳为你收集整理的luogu P3275 [SCOI2011]糖果背景：题目传送门：题意：思路：代码：的全部内容，希望文章能够帮你解决luogu P3275 [SCOI2011]糖果背景：题目传送门：题意：思路：代码：所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。