题目： 排队吃饭
小结：
差分约束：即将一些不等关系转换为图上帯权边，再通过 $SPFA$ 或 $DFS$ 求解。
- 寻找不等关系，再将建立的方程转化为 $ d[a] - d[b] \leq c$ 的形式。
- 将 $ d[a] - d[b] \leq c$ 转化为一条由点 $b$ 指向点 $a$ 权值为 $c$ 的边。
- 对于存在性问题，判断其是否存在负环。
参考 ： 1
代码实现
#include <iostream>
#include <cstdio>
using namespace std;
struct NodePath{//边
int Next_out, c, v;
NodePath (int a = 0, int b = 0, int d = 0)
{
Next_out = a;
c = b;
v = d;
}
} ph[30000 + 9];
struct NodePoint{//点
int Head_out, dis;
bool In_queue, vis;
NodePoint (int a = 0, int b = 0x3f3f3f3f, bool c = false, bool d = false)
{
Head_out = a;
dis = b;
In_queue = c;
vis = d;
}
} pt[1000 + 9];
void addnode (int u, int v, int c);//建边
bool dfs (int s);
void GrandNew ();
void outt (int n);
int e = 0;
int main()
{
int N, L, UL;
while (cin >> N >> L >> UL)
{
GrandNew();//初始化
// e = 0;
for (int i = 1; i <= L; i++)//条件Ⅰ
{
int a, b, d;
cin >> a >> b >> d;
addnode (a, b, d);
}
for (int i = 1; i <= UL; i++)//条件Ⅱ
{
int a, b, d;
cin >> a >> b >> d;
addnode (b, a, -d);
}
for (int i = 1; i < N; i++)//条件Ⅲ，条件Ⅳ
{
addnode (i+1, i, 0);
}
pt[1].dis = 0;
outt(N);
}
}
void outt(int N)
{
for (int i = 1; i <= N; i++)
{
if (dfs(i) == false)//负环
{
cout << "-1" << endl;
return ;
}
}
if (pt[N].dis == 0x3f3f3f3f)
{
cout << "-2" << endl;
return ;
}
cout << pt[N].dis << endl;
return ;
}
void GrandNew ()
{
for (int i = 1; i <= 30000; i++)
ph[i] = NodePath();
for (int i = 1; i <= 1000; i++)
pt[i] = NodePoint();
e = 0;
}
bool dfs(int s)
{
// if (pt[s].vis) return true;//永久标记：该点已访问过
pt[s].In_queue = true;//短期标记：该点正在访问中
for (int i = pt[s].Head_out; i; i = ph[i].Next_out)//枚举 s 点所有出边
{
int z = ph[i].v;//枚举所有终点
if (pt[z].dis > pt[s].dis + ph[i].c)
{
pt[z].dis = pt[s].dis + ph[i].c;
if (pt[z].In_queue) return false;
if (!dfs(z)) return false;
}
}
pt[s].In_queue = false;
// pt[s].vis = true;
return true;
}
void addnode (int u, int v, int c)
{
e++;
ph[e].Next_out = pt[u].Head_out;
pt[u].Head_out = e;
ph[e].c = c;
ph[e].v = v;
}
