差分约束算法

差分约束算法

一 定义

 差分约束算法通常用于解决差分约束算法==(属于线性规划)==,解决差分约束问题我们通常将它转化为最短路或者最长路问题，比如我们有如下的差分关系$$\{\begin{array}{ll}& x_1-x_2>3\\ & x_2-x_3>2\\ & ...\end{array}$$​​，我们可以将每一个变元都看作是一个点，$$x_1-x_2>3$$可以转化为一条从$x_2$到$x_1$的一条长度为3的边。在这种关系之下我们可以得到一条最短路。使得满足这种最短的关系。得到最短路之后，得到最短路之后再进行判读是否满足每一个差分

约束的关系，如果满足，则可行。

二 模版题and code

差分约束模版题

#include <iostream>
using namespace std;
struct node{
    int from , to , dis;
};
node e[5010];
int n , m;
int dis[5010];
int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> e[i].to >> e[i].from >> e[i].dis;  
    for(int i = 1; i <= n - 1; i++)
        for(int j = 1; j <= m; j++)
            dis[e[j].to] = min(dis[e[j].to] , dis[e[j].from] + e[j].dis);  
    for(int j = 1; j <= m; j++)
        if(dis[e[j].to] > dis[e[j].from] + e[j].dis){ 
            cout << "NO";
            return 0;
        }
    for(int i = 1; i <= n; i++) cout << dis[i] << " ";
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23