[SCOI2011]糖果（差分约束系统）

转换题目所给的关系式(参考cxr大佬

$A=B$，可拆为$Age B,Bge A$，即为$A-Bge 0,B-Age 0$ (X=1)

$A<B$，改写为$Ale B-1$，即为$B-Age 1$ (X=2)

$Age B$，即为$A-Bge 0$ (X=3)

$A>B$，改写为$A-1ge B$，即为$A-Bge 1$ (X=4)

$Ale B$，即为$Bge A$ (X=5)

根据转换后的关系式建边，用SPFA跑一遍最长路即可~

最后答案为$sum_{i=1}^{n}dis[i]$。

代码

 1 #include<bits/stdc++.h>
 2 #define N 300000+5
 3 using namespace std;
 4 int n,k,cnt,dis[N],fro[N],tot[N];
 5 bool vis[N];
 6 struct edge{int to,w,nxt;}a[N];
 7 queue<int>q;
 8 inline int read() {
 9     int x=0; char c=getchar();
10     while(c<'0'||c>'9') c=getchar();
11     while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
12     return x;
13 }
14 void add(int x,int y,int z) {
15     a[++cnt].to=y,a[cnt].w=z,a[cnt].nxt=fro[x]; fro[x]=cnt;
16 }
17 
18 void SPFA() {
19     q.push(0),vis[0]=1; 
20     while(!q.empty()) {
21         int x=q.front(); q.pop();
22         vis[x]=0,tot[x]++;
23         if(tot[x]==n) {puts("-1"); exit(0);}
24         for(int i=fro[x];i;i=a[i].nxt) {
25             int y=a[i].to;
26             if(dis[y]<dis[x]+a[i].w) {
27                 dis[y]=dis[x]+a[i].w;
28                 if(!vis[y]) q.push(y),vis[y]=1;
29             }
30         }
31     }
32 }
33 
34 int main() {
35     n=read(),k=read();
36     while(k--) {
37         int x=read(),a=read(),b=read();
38         if(a==b&&(x==2||x==4)) return puts("-1"),0;
39         switch(x) {
40             case 1:add(a,b,0),add(b,a,0); break;
41             case 2:add(a,b,1); break;
42             case 3:add(b,a,0); break;
43             case 4:add(b,a,1); break;
44             case 5:add(a,b,0); break;
45         }
46     }
47     for(int i=n;i>0;i--) add(0,i,1); 
48     SPFA();
49     long long ans=0;
50     for(int i=1;i<=n;i++) ans+=dis[i];
51     printf("%lld",ans);
52 }