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

问题描述

1. acwing.
2. 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;
}

总结

坑还是挺多的：
1.spfa中如果用queue，有负环的话会超时，这里要用stack玄学优化。
2.M要开3倍N,不然就会TLE。
3.会爆int。