差分约束系统---1且2--2022年5月27日

为了避免最坏情况的出现，在正权图上应使用效率更高的Dijkstra算法。

Dijkstra算法

选择特殊路径长度最短的路径，将其连接的V-S中的顶点加入到集合S中，同时更新数组dist[]。一旦S包含了所有顶点，dist[]就是从源到所有其他顶点的最短路径长度。
（1）数据结构。 
           设置地图的带权邻接矩阵为map[][]，即如果从源点u到顶点i有边，就令map[u][i]=<u,i>的权值，否则map[u][i]=∞；
		      采用一维数组dist[i]来记录从源点到i顶点的最短路径长度：采用一维数组p[i]来记录最短路径上i顶点的前驱。
（2）初始化。
        令集合S={
    u}，对于集合V-S中的所有顶点x，初始化dist[i]=map[u][i],如果源点u到顶点i有边相连，初始化p[i]=u(i的前驱是u),否则p[i]=-1
（3）找最小。
      在集合V-S中依照贪心策略来寻找使得dist[j]具有最小值的顶点t,即dist[t]=min，则顶点t就是集合V-S中距离源点u最近的顶点。
（4）加入S战队。将顶点t加入集合S，同时更新V-S
（5）判结束。如果集合V-S为空，算法结束，否则转6
（6）借东风。在（3）中已近找到了源点到t的最短路径，那么对集合V-S中所有与顶点t相邻的顶点j，都可以借助t走捷径。
			如果dist[j]>dist[t]+map[t][j],则dist[j]=dist[t]+map[t][j]，记录顶点j的前驱为t，p[j]=t，转（3）。
			//我自己在这里理解就是，从u找到与它最近的点t，在从t找到与它最近的点j，在....按照这样持续下去，直到最后一个点
	这里我再通俗的解释下这个借东风的意思。
	源点为1，如果我们找到了距离源点最近的点2，且点2与3,4相连。
		这样，我们如果要倒3,4有两种方法：
				1->2->3(4)
				1->3(4)
		这里我们就要判断是从1直接到3(4)快，还是经过2后快。假设<1,2>=2 / <2,3>=3 / <1,3>=4
			根据上面的数据，我们第一次找最小找到的是2结点，如果我们直接把2替换掉1当做源点继续找下一个最近的点，这种方法是错的。
			因为可以看出1->3只用4，而过2的话要用5。

以下是代码

#include<bits/stdc++.h>
using namespace std;
const int N=100;	//城市个数可修改
const int INF=1e7;	//初始化无穷大为.......
int map[N][N],dist[N],p[N],n,m;	//n为城市个数，m为城市间路线的条数
bool flag[N];	//如果flag[i]=true,说明该顶点i已经加入到集合S；否则i属于集合V-S

void Dijkstra(int u){
    
	for(int i=1;i<=n;i++){
    //********>>>--1--<<<******//
		dist[i]=map[u][i];	//初始化源点u到其他各个顶点的最短路径长度
		flag[i]=false;
		if(dist[i]==INF)
			p[i]=-1;	//说明源点u到顶点i无边相连，设置p[i]=-1
		else
			p[i]=u;	//说明源点u到顶点i有边相连，设置p[i]=u
	}
	flag[u]=true;//初始化集合S中，只有一个元素：源点u
	dist[u]=0;	//初始化源点u的最短路径为0，自己到自己的最短路径
	for(int i=1;i<=n;i++){
    //********>>>--2--<<<******//
		int temp=INF,t=u;
		for(int j=1;j<=n;j++){
    //>>--3--<<在集合V-S中寻找距离源点u最近的顶点t
			if(!flag[j] && dist[j]<temp){
    
				t=j;	//记录距离源点u最近的顶点
				temp=dist[j];
			}
		}
		if(t==u) return ;	//找不到t跳出循环
		flag[t]=true;	//否则，将t加入集合S
		for(int j=1;j<=n;j++){
    //>>--4--<<更新集合V-S中与t邻接的顶点到u的距离
			if(!flag[j] && map[t][j]<INF){
    //！flag[j]表示j在v-s集合中，map[t][j]<INF表示t与j邻接
				if(dist[j]>(dist[t]+map[t][j])){
    //经过t到达j的路径更短
					dist[j]=dist[t]+map[t][j];
					p[j]=t;	//记录j的前驱为t
				}
			}
		}	
	}	
}

int main(){
    
		int u, v, w, st;
	system("color 0d");
	cout << "请输入城市的个数：" << endl;
	cin >> n;
	cout << "请输入城市之间的路线个数" << endl;
	cin >> m;
	cout << "请输入城市之间的路线以及距离" << endl;
	for(int i=1;i<=n;i++)//初始化图的邻接矩阵
		for (int j = 1; j <= n; j++)
		{
    
			map[i][j] = INF;//初始化邻接矩阵为无穷大
		}
	while (m--)
	{
    
		cin >> u >> v >> w;
		map[u][v] = min(map[u][v], w);	//邻接矩阵存储，保留最小的距离
	}
	cout << "请输入小明所在的位置：" << endl;
	cin >> st;
	Dijkstra(st);
	cout << "小明所在的位置：" << st << endl;
	for (int i = 1; i <= n; i++)
	{
    
		cout << "小明：" << st << " - " << "要去的位置：" << i << endl;
		if (dist[i] == INF)
			cout << "sorry,无路可达" << endl;
		else
			cout << "最短距离为：" << dist[i] << endl; 
	}
	return 0;
}

若给定的图存在负权边，类似Dijkstra算法等算法便没有了用武之地，SPFA算法便派上用场了。简洁起见，我们约定加权有向图G不存在负权回路，即最短路径一定存在。用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。

bellman-ford算法

允许负数环，即允许边权值为负数。
只能做判断，不能算出权值。
松弛算法，对边松弛，dijkstra 算法的一些推论。

找到最大值与最小值的差值。
可以构建约束图

用邻接表结构实现bellman_ford

//邻接表的结构
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 0x3f3f3f3f
#define N 1010
int nodenum, edgenum, original; //点，边，起点
typedef struct Edge //边
{
    
	int u, v;
	int cost;
}Edge;
Edge edge[N];
int dis[N], pre[N];
void init()
{
    
	int i = 0, x = 0, y = 0, c = 0;
	cin>>nodenum>>edgenum>>original;
	//pre[original] = original;
	for (int i = 1; i <= edgenum; ++i)
	{
    
		cin >>edge[i].v>>edge[i].u>> edge[i].cost;
	}
}
bool Bellman_Ford()
{
    
	for (int i = 1; i <= nodenum - 1; ++i)
		for (int j = 1; j <= edgenum; ++j)
			if (dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛（顺序一定不能反~）
			{
    
				dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;
				//pre[edge[j].v] = edge[j].u;
			}
	bool flag = 1; //判断是否含有负权回路
	for (int i = 1; i <= edgenum; ++i)
		if (dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)
		{
    
			flag = 0;
			break;
		}
	return flag;
}
void print_path(int root) //打印最短路的路径（反向）
{
    
	while (root != pre[root]) //前驱
	{
    
		printf("%d-->", root);
		root = pre[root];
	}
	if (root == pre[root])
		printf("%d\n", root);
}
int main()
{
    
	init();
	Bellman_Ford();
	for (int i = 0; i <= nodenum; i++)
	{
    
		cout << dis[i] << " ";
	}
	return 0;
}

用邻接矩阵实现bellman_ford

//邻接矩阵
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
#define MAX 0x3f3f3f3f
#define N 1010
int nodenum, edgenum, original; //点，边，起点
int map[N][N];  //邻接矩阵
int dis[N];

void init()
{
    
	int i = 0, x = 0, y = 0, c = 0;
	cin >> nodenum >> edgenum ;
	//pre[original] = original;
	for (i = 0; i < nodenum; i++)
	{
    
		for (int j = 0; j < nodenum; j++)
		{
    
			map[i][j] = 9;
		}
	}
	for (i = 1; i <= edgenum; ++i)
	{
    
		cin >> x>> y >> c;
		map[y][x] = c;
	}
	for (i = 0; i <= nodenum; i++)
	{
    
		map[0][i] = 0; //定一个标准，最小都是0。
	}
	memset(dis, 0, sizeof(dis));
}

void bellman_ford(int v)
{
    
	int i = 0;
	for (i = 0; i < nodenum; i++)
	{
    
		dis[i] = map[0][i];
	}
	bool flag = 1;
	for (int k = 2; k <= nodenum; k++)//这个是次数的循环，只要走边数减一即可
	{
    
		flag = 1;
		for(int u=1;u<=nodenum;u++)
		if (u != 0)//不是起点
		{
    
			for (i = 1; i <= nodenum; i++)
			{
    
				if (dis[i]>dis[u] + map[u][i])
				{
    
					dis[i] = dis[u] + map[u][i];
					flag = 0;
				}
			}
		}
	}
	if (flag = 0)
	{
    
		cout << "有负数圈" << endl;
	}
}
int main()
{
    
	init();
	bellman_ford(0);
	for (int i =0; i <= nodenum; i++)
	{
    
		cout << dis[i] << " ";
	}
	cout << endl;
	return 0;
}

SPFA算法 ----Bellman-Ford算法 的队列优化算法的别称

struct edge {
    
    int v, w, fail;
    edge() {
    }
    edge(int _v, int _w, int _fail) {
    
        v = _v;
        w = _w;
        fail = _fail;
    }
} e[M << 1];
bool spfa(int u) {
    
    memset(vis, false, sizeof(vis));
    vis[u] = true;
    memset(dis, -1, sizeof(dis));  //因为是最长路，故要初始化为负数
    dis[u] = 0;
    memset(in, 0, sizeof in);
    in[u] = 1;
    queue<int> q;
    q.push(u);
    while (!q.empty()) {
    
        u = q.front();
        q.pop();
        vis[u] = false;
        for (int j = head[u]; ~j; j = e[j].fail) {
    
            int v = e[j].v;
            int w = e[j].w;
            if (dis[v] < dis[u] + w) {
     // 求最长路，和求最短路相反
                dis[v] = dis[u] + w;
                if (!vis[v]) {
    
                    q.push(v);
                    vis[v] = true;
                    ++in[v];
                    if (in[v] > n + 1) {
      //判断负环，因为加了一个超级源点，故应跟 n + 1 而不是 n 比较。
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

洛谷P5960 【模板】差分约束算法 题解

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 50005;
const int M = 50005;

struct edge {
    
    int v, w, fail;
    edge() {
    }
    edge(int _v, int _w, int _fail) {
    
        v = _v;
        w = _w;
        fail = _fail;
    }
} e[M];
int head[N], len;
void init() {
    
    memset(head, -1, sizeof(head));
    len = 0;
}
void add(int u, int v, int w) {
    
    e[len] = edge(v, w, head[u]);
    head[u] = len++;
}
int n, m;
int dis[N], in[N];
bool vis[N];
bool spfa(int u) {
    
    memset(vis, false, sizeof(vis));
    vis[u] = true;
    memset(dis, -1, sizeof(dis));
    dis[u] = 0;
    memset(in, 0, sizeof in);
    in[u] = 1;
    queue<int> q;
    q.push(u);
    while (!q.empty()) {
    
        u = q.front();
        q.pop();
        vis[u] = false;
        for (int j = head[u]; ~j; j = e[j].fail) {
    
            int v = e[j].v;
            int w = e[j].w;
            if (dis[v] < dis[u] + w) {
    
                dis[v] = dis[u] + w;
                if (!vis[v]) {
    
                    q.push(v);
                    vis[v] = true;
                    ++in[v];
                    if (in[v] > n + 1) return true;
                }
            }
        }
    }
    return false;
}

int main() {
    
    init();
    int u, v, w, op;
    cin >> n >> m;
    while (m--) {
    
        cin >> u >> v >> w;
        add(u, v, -w);
    } 
    for (int i = 1; i <= n; ++i) add(0, i, 0);
    if (spfa(0)) cout << "NO" << endl;
    else for (int i = 1; i <= n; ++i) cout << dis[i] << " ";
    return 0;
}

差分约束，是一个建模的思想。

也就是把一些代数上的约束关系建模成图论的相关问题。差分约束的一些题目往往对思维上建模能力的要求比较高，而对具体算法的考察却比较低，所以做差分约束的题目，一般建模之后会给人一种敲板子的那种流畅和虐题的感觉哈哈哈哈。

作业2770

仍然有问题的代码

//spfa+slf优化
#include<cstdio>
#include<iostream>
#define mx 999999
using namespace std;

int n;      // 一共有N个大营
int m;      //已知 从第i 个大营到第j个大营至少有多少士兵
int c[1001]; // 第i个大营最多有C[i]个士兵
int dist[1001]; //最少的兵营的士兵个数 a
int S[1001];  //前i 个大营的容量 d
const int mn = 23000;
int ei; //边的序号
struct Edge
{
    
    int start;
    int end;
    int cost; 
} edge[mn];

void init()
{
    
    ei = 0;
    int i;
    for (i = 0; i <= n; i++)
        dist[i] =0;
    dist[0] = 0;
    S[n] = 0;  //一开始初始化所有士兵总数为0
}


bool bellman_ford()
{
    
    int i, k, t;
    for (i = 0; i < n; i++)
    {
    
        /* 假设第K条边的起点是u ， 终点是v, 下面循环考虑第k 条边是否会使得源点V0到v 的最短距离缩短 */
        for (k = 0; k < ei; k++)
        {
    
            if (dist[edge[k].start] != mx && dist[edge[k].start] + edge[k].cost < dist[edge[k].end]) //经典三角公式
            {
    
                dist[edge[k].end] = dist[edge[k].start] + edge[k].cost;
            }
        }
    }
    for (k = 0; k < ei; k++)
    {
    
        if (dist[edge[k].start] != mx && dist[edge[k].end] + edge[k].cost < edge[k].end)
            return false;//有回路
    }
    return true;
}
int main()
{
    
    while (cin>>n>>m)
    {
    
        init();
        int i,u, v, w;
        for (int i = 1; i <= n; ++i)
        {
    
            cin >> c[i];
            edge[ei].start = i - 1;
            edge[ei].end = i;  //构造边<i-1, i> 每一个兵营的数量是
            edge[ei].cost = c[i];
            ei++;
            //边 <i, i-1 > 这个权值为0
            edge[ei].start = i;
            edge[ei].end = i - 1;
            edge[ei].cost = 0;
            ei++;
            S[i] = c[i] + S[i - 1];
        }
        for (i = 0; i < m; i++)
        {
    
            cin >> u >> v >> w;
            edge[ei].start = v; edge[ei].end = u-1;
            edge[ei].cost = -w;
            ei++;
            edge[ei].start = u - 1;
            edge[ei].end = v;
            edge[ei].start = S[v] - S[u - 1];
            ei++;
        }
        if (!bellman_ford())
            cout << dist[n] - dist[0] << endl;
        else
            cout << "Bad Estimations" << endl;
    }
    return 0;
}
/* 3 2 1000 2000 3000 1 2 1100 2 3 1300 3 1 100 200 300 2 3 600 */