【解题报告】洛谷P3275 糖果

原题链接

https://www.luogu.com.cn/problem/P3275

思路

在这样天气寒冷的日子里，怎么能不做题呢~！

天气阴凉，我怀着激动的心情打开了这道题目

题意大概满足一堆要求，让你求一个满足要求的所有的变量的和

自己看去吧

然后我们读题发现，这不就是一个差分约束吗？

待会？

差分约束满足的形式是这样的
xi−xi′≤yi x_i-x_{i'} \le y_i
所以题目中不少于不多于的都非常好搞，直接连边就可以了

那剩下的怎么搞呢？

首先等于，等于的话我们可以双向连边，一个不大于，一个不小于，不就是等于了吗？

然后后面呢？

我们实际上可以他们变成 A≤B−1A \le B-1 , B≤A−1B \le A-1 之类的，这样就可以实现小于了，具体这样做的原因是因为 A,BA,B 只能是整数啊喂

然后我们用一个 SPFASPFA 跑就可以了

有一个玄学的东西，就是我们在跑的时候要对于超级源点从大边向小边连边，不然会被卡掉，或者连边的同时把连得边都 push 一下也可以似乎？

我不知道为啥，但是我过了

别人也不知道为啥，我就写在了这里qaq

std

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#define int long long
using namespace std;
const int maxn=300005;
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
		f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
struct edge{
	int e,next,val;
}ed[maxn<<1];
int en,first[maxn];
void add_edge(int s,int e,int val)
{
	en++;
	ed[en].next=first[s];
	first[s]=en;
	ed[en].e=e;
	ed[en].val=val;
}
int n,k;
int d[maxn],num[maxn];
bool vis[maxn];
queue <int> q;
bool spfa(int s)
{
	d[s]=0;
	vis[s]=true;
	q.push(s);
	num[s]++;
	while(q.size())
	{
		int x=q.front();
		q.pop();
		vis[x]=false;
		for(int i=first[x];i;i=ed[i].next)
		{
			int e=ed[i].e;
			int val=ed[i].val;
			if(d[e]<d[x]+val)
			{
				d[e]=d[x]+val;
				if(!vis[e])
				{
					vis[e]=true;
					q.push(e);
					num[e]++;
					if(num[e]==n+1) return false;
				}
			}
		}
	}
	return true;
}
signed main()
{
	memset(d,-0x3f3f3f,sizeof(d));
	n=read(),k=read();
	for(int i=1;i<=k;i++)
	{
		int x=read(),a=read(),b=read();
		if(x==1)
		{
			add_edge(b,a,0);//a<=b
			add_edge(a,b,0);//a>=b;
		}
		else if(x==2)
		{
			if(a==b)
			{
				cout<<-1<<'\n';
				return 0;
			}
			add_edge(a,b,1);//a<b
		}
		else if(x==3)
		{
			add_edge(b,a,0);//a>=b
		}
		else if(x==4)
		{
			if(a==b)
			{
				cout<<-1<<'\n';
				return 0;
			}
			add_edge(b,a,1);//a>b
		}
		else if(x==5)
		{
			add_edge(a,b,0);//a<=b
		}
	}
	for(int i=n;i>=1;i--)
	add_edge(0,i,1);//q.push(i);
	if(!spfa(0))
	{
		cout<<-1<<'\n';
		return 0;
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	ans+=d[i];
	cout<<ans<<'\n';
	return 0;
}