差分约束
屈服于spfa（用堆优化dj蜜汁TLE）
差分约束模板题吧（大概）
但是数据很毒瘤。
对于5种情况，我们发现这都是A-B>=0/1 或 B-A>=0/1 的形式
我们可以转化为 B+0/1 <= A ，也就是求最长路
但是我写的dj被卡了。于是就用spfa在150ms内过了（大雾）
注意判正环，这样是无解的。
attention：答案爆int；有一些sb小朋友会提出无理的要求，比如自己拿的糖果要比自己少（这样分个球）
#include<iostream> #include<cstdio> #include<cstring> #include<cctype> #include<queue> using namespace std; template <typename T> inline T min(T &a,T &b) {return a<b ?a:b;} template <typename T> inline void read(T &x){ char c=getchar(); x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar(); } queue <int> h; int n,m,s,vis[100005]; long long ans,d[100005]; bool v[100005],ok=1; int cnt,hd[100005],nxt[200005],ed[100005],poi[200005],val[200005]; inline void add(int x,int y,int v){ nxt[ed[x]]=++cnt; hd[x]= hd[x] ? hd[x]:cnt; ed[x]=cnt; poi[cnt]=y; val[cnt]=v; if(x==y&&v) ok=0; //自正环 } int main(){ read(n); read(m); int q1,q2,q3; s=n+1; for(int i=1;i<=m;++i){ read(q1); read(q2); read(q3); if(!ok) continue; switch(q1){ //5种情况分别连边 case 1:{add(q2,q3,0); add(q3,q2,0); break;} case 2:{add(q2,q3,1); break;} case 3:{add(q3,q2,0); break;} case 4:{add(q3,q2,1); break;} case 5:{add(q2,q3,0); break;} } } for(int i=1;i<=n;++i) add(s,i,1); //设一个虚拟起点 h.push(s); d[s]=0; v[s]=1; while(!h.empty()&&ok){ //spfa求最长路 int x=h.front(); h.pop(); v[x]=0; if(++vis[x]>=n) {ok=0; break;} for(int i=hd[x];i;i=nxt[i]) if(d[x]+val[i]>d[poi[i]]){ d[poi[i]]=d[x]+val[i]; if(!v[poi[i]]) v[poi[i]]=1,h.push(poi[i]); } } if(!ok) {printf("-1"); return 0;} for(int i=1;i<=n;++i) ans+=d[i]; //累加权值 printf("%lld",ans); return 0; }