[模板_差分约束]AcWing 1169. 糖果

本文主要是介绍[模板_差分约束]AcWing 1169. 糖果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

AcWing 1169. 糖果

问题描述
具体分析
具体代码
总结

问题描述

acwing.
LUOGU.

具体分析

个人理解：
1.差分约束问题就是一种把这类问题抽象出图，然后利用最短路算法去求解。是最短路的一个经典应用。
2.但是在具体的代码实现中，会遇到许多问题。例如：一般spfa求负环会TLE；虚拟源点（超级远点）的建立……
3.具体实现思想：利用最短路问题中的不等性质，将问题中的不等关系转化成图中的带权边，再根据——“求最小值跑最长路，求最大值跑最短路”的结论，用spfa求解dist数组。

具体代码

#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 10,M = 3 * N;//因为有超级源点，所以要开三倍的边typedef long long LL;//会爆intint h[N],e[M],ne[M],w[M],idx;
int n,k;
bool st[N];//spfa必备
LL dist[N];
int cnt[N];//求负环必备
void add(int a,int b,int c)
{e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}bool spfa()
{memset(dist,-0x3f,sizeof dist);//因为是求最长路，所以初始化成负的dist[0]=0;stack<int> q;q.push(0);st[0]=true;while(q.size()){auto t = q.top();q.pop();st[t]=false;for(int i=h[t];~i;i=ne[i]){int j=e[i];if(dist[j]<dist[t]+w[i]){dist[j]=dist[t]+w[i];cnt[j] = cnt[t] + 1;if(cnt[j]>n)    return false;//存在负环if(!st[j])  {q.push(j);st[j]=true;}}}}return true;
}int main()
{scanf("%d%d",&n,&k);memset(h,-1,sizeof h);for(int i=0;i<k;i++){int x,a,b;scanf("%d%d%d",&x,&a,&b);if(x==1)//重点！！建边时一定要在纸上写清楚如何将不等式转换成边add(a,b,0),add(b,a,0);else if(x==2)   add(a,b,1);else if(x==3)   add(b,a,0);else if(x==4)   add(b,a,1);else add(a,b,0);}for(int i=1;i<=n;i++)//建立超级源点{add(0,i,1);}if(!spfa()) puts("-1");else{LL ans = 0;for(int i=1;i<=n;i++)ans+=dist[i];printf("%lld",ans);}return 0;
}