题解

题目类型：差分约束系统（Difference Constraints）
算法核心：建图转化 + 最长路 SPFA（带 SLF 优化）+ 正环（>0 环）判不可行

一、题意抽象与建模

设有 n 个变量 (x_1,\dots,x_n)，题面给出 k 条关系/约束。将它们统一转化为差分约束的边： [ x_v \ge x_u + w \quad \Longleftrightarrow \quad \text{add edge } u \to v \text{ with weight } w . ]

代码中的 5 类操作与边的意义（记 a、b 为输入）：

此外，为了满足“最小下界”，给一个超级源 (s)（代码里 s=0），连边： [ s \to i \text{ 权 } 1 \quad (1 \le i \le n) ] 表示 (x_i \ge 1)。
最终我们需要在所有约束可行的前提下，使 (\sum_i x_i) 尽量大。这等价于：以 s 为源，求每个点的最长路径值 dis[i]，答案即 (\sum_i \text{dis}[i])。

若系统不可行，将出现“可以无限增大的环”，即正权环（>0 环），此时输出 -1。

二、为什么是“最长路”而不是“最短路”？

• 边 (u\to v) 权 (w) 表示 (x_v \ge x_u + w)。
• 若从 s 出发做最长路松弛：
  dis[v] = max(dis[v], dis[u] + w)
  即不断抬高下界，得到满足全部约束的最大可行下界集合（极大解）。
• 一旦存在正环，可以让 dis 沿环无限增大，系统无解（不可行）。

三、判不可行：SPFA 计数法

• 令 cnt[v] 统计结点 v 被入队/松弛的次数；
• 如果某点 cnt[v] > n，说明存在正环（因为最长路版的“Bellman-Ford”若超过 n-1 次仍能松弛，一定有 >0 环），直接输出 -1 退出。

四、队列优化：SLF + 环形队列

函数 spfa_slf() 采用 SLF（Small Label First） 策略与手写环形队列加速：

• SLF：当 v 要入队时，若 dis[v] > dis[q[head]]，就把 v 插到队头（更“急”的点更早处理），否则插队尾；
• 自写环形数组 q[]、head/tail + again 计数，避免 deque 的常数开销。

这两点能显著提升 SPFA 在随机数据上的表现。

五、正确性与边界

• 若 (opt==2 || opt==4) && a==b，约束形如 (x_a \ge x_a + 1)，直接矛盾，立即输出 -1（代码中已处理）。
• 初值：dis[] 默认全 0；由 s→i 权 1 的边保证 dis[i] 至少能被推到 1，从而得到最大可行下界。
• 只要不出现 cnt[v] > n，最终 dis[] 即为所有约束下的极大可行解，答案为其和。

六、复杂度

• 理论最坏 SPFA 可到 (O(nm))，但本题存在 SLF 与剪枝，且差分约束图结构较规整，实际表现接近线性；
• 空间 (O(n+m))。

七、代码（与题给一致）

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+10;
int n,k,s;
vector<pair<int,int> > G[MAXN];
inline void add(int u,int v,int w){
	G[u].push_back({v,w});
	return ;
}
bool vis[MAXN]; int dis[MAXN],cnt[MAXN];
int q[MAXN],head=0,tail=1,again=0,maxn=MAXN-10;
inline void spfa_slf(){
	q[head]=s; dis[s]=0; vis[s]=true; cnt[s]++;
	while(head<tail+maxn*again){
		if(head>maxn){head%=maxn; again--;}
		int u=q[head]; head++; vis[u]=false;
		for(auto [v,w]:G[u]){
			if(dis[v]<dis[u]+w){
				dis[v]=dis[u]+w;
				if(!vis[v]){
					if(dis[v]>dis[q[head]] && head-1>=0) --head,q[head]=v;
					else{
						if(tail>maxn){again++; tail%=maxn;}
						q[tail]=v; tail++;
					}
					cnt[v]++;
					if(cnt[v]>n){cout<<-1<<'\n'; exit(0);}
					vis[v]=true;
				}
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k; 
	for(int i=1;i<=n;i++) add(s,i,1);
	for(int i=1;i<=k;i++){
		int opt,a,b; cin>>opt>>a>>b;
		if((opt==2 || opt==4) && a==b) return cout<<-1<<'\n',0;
		switch (opt){
			case 1: add(a,b,0),add(b,a,0); break;
			case 2: add(a,b,1); break;
			case 3: add(b,a,0); break;
			case 4: add(b,a,1); break;
			case 5: add(a,b,0); break;
			default: break;
		}
	}
	spfa_slf(); 
	long long ans=0;
	for(int i=1;i<=n;i++) ans+=dis[i];
	cout<<ans<<'\n';
	return 0;
}