Differential restraint system -- 1 and 2 -- May 27, 2022

To avoid the worst , Higher efficiency should be used on the positive weight diagram Dijkstra Algorithm .

Dijkstra Algorithm

 Select the path with the shortest special path length , Connected V-S Add vertices from to the set S in , Update the array at the same time dist[]. once S Contains all vertices ,dist[] Is the shortest path length from the source to all other vertices .
（1） data structure . 
            Set the weighted adjacency matrix of the map to map[][], That is, if from the source u To the top i Have edge , Order map[u][i]=<u,i> A weight , otherwise map[u][i]=∞;
		       Using one-dimensional array dist[i] To record from the source point to i The shortest path length of the vertex ： Using one-dimensional array p[i] To record the shortest path i The precursor of the vertex .
（2） initialization .
         Let's get together S={
    u}, For collection V-S All the vertices in x, initialization dist[i]=map[u][i], If the source point u To the top i It's connected by sides , initialization p[i]=u(i The precursor to this is u), otherwise p[i]=-1
（3） Look for the smallest .
       In collection V-S In accordance with the greedy strategy to find to make dist[j] Vertex with minimum value t, namely dist[t]=min, Then the summit t It's a collection V-S Medium distance source point u Nearest vertex .
（4） Join in S team . Put the vertex t Join the collection S, Simultaneous updating V-S
（5） End of judgment . If the collection V-S It's empty , The algorithm ends , Otherwise turn 6
（6） Borrow the east wind . stay （3） We have found the source point to t Shortest path , So for the set V-S All and vertices in t Adjacent vertices j, You can use t Take a shortcut .
			 If dist[j]>dist[t]+map[t][j], be dist[j]=dist[t]+map[t][j], Record vertices j The precursor of t,p[j]=t, turn （3）.
			// My own understanding here is , from u Find the nearest point to it t, In from t Find the nearest point to it j, stay .... Continue like this , Until the last point 
	 Here I will explain the meaning of borrowing the east wind in a popular way .
	 The source point is 1, If we find the point closest to the source 2, And the point 2 And 3,4 Connected to a .
		 such , If we want to fall 3,4 There are two ways ：
				1->2->3(4)
				1->3(4)
		 Here we have to judge from 1 Direct to 3(4) fast , Or after 2 Back fast . hypothesis <1,2>=2 / <2,3>=3 / <1,3>=4
			 According to the data above , The first time we looked for the smallest one was 2 node , If we just 2 Replace 1 As the source point, continue to find the next nearest point , This approach is wrong .
			 Because you can see 1->3 Only 4, And pass by 2 If you want to use 5.

Here's the code

#include<bits/stdc++.h>
using namespace std;
const int N=100;	// The number of cities can be modified 
const int INF=1e7;	// Initialize infinity to .......
int map[N][N],dist[N],p[N],n,m;	//n Number of cities ,m Is the number of routes between cities 
bool flag[N];	// If flag[i]=true, Explain the vertex i Has been added to the collection S; otherwise i Belong to a collection V-S

void Dijkstra(int u){
    
	for(int i=1;i<=n;i++){
    //********>>>--1--<<<******//
		dist[i]=map[u][i];	// Initialize the source point u The shortest path length to each other vertex 
		flag[i]=false;
		if(dist[i]==INF)
			p[i]=-1;	// Explain the source u To the top i Boundless connection , Set up p[i]=-1
		else
			p[i]=u;	// Explain the source u To the top i It's connected by sides , Set up p[i]=u
	}
	flag[u]=true;// Initialize collection S in , There's only one element ： Source point u
	dist[u]=0;	// Initialize the source point u The shortest path is 0, The shortest path from oneself to oneself 
	for(int i=1;i<=n;i++){
    //********>>>--2--<<<******//
		int temp=INF,t=u;
		for(int j=1;j<=n;j++){
    //>>--3--<< In collection V-S Find the distance source in u Nearest vertex t
			if(!flag[j] && dist[j]<temp){
    
				t=j;	// Record the distance from the source u Nearest vertex 
				temp=dist[j];
			}
		}
		if(t==u) return ;	// Can't find t Out of the loop 
		flag[t]=true;	// otherwise , take t Join the collection S
		for(int j=1;j<=n;j++){
    //>>--4--<< Update collection V-S China and t Adjacent vertices to u Distance of 
			if(!flag[j] && map[t][j]<INF){
    //！flag[j] Express j stay v-s Collection ,map[t][j]<INF Express t And j Adjacency 
				if(dist[j]>(dist[t]+map[t][j])){
    // after t arrive j The path is shorter 
					dist[j]=dist[t]+map[t][j];
					p[j]=t;	// Record j The precursor of t
				}
			}
		}	
	}	
}

int main(){
    
		int u, v, w, st;
	system("color 0d");
	cout << " Please enter the number of cities ：" << endl;
	cin >> n;
	cout << " Please enter the number of routes between cities " << endl;
	cin >> m;
	cout << " Please enter the route and distance between cities " << endl;
	for(int i=1;i<=n;i++)// Initialize the adjacency matrix of the graph 
		for (int j = 1; j <= n; j++)
		{
    
			map[i][j] = INF;// Initialize the adjacency matrix to infinity 
		}
	while (m--)
	{
    
		cin >> u >> v >> w;
		map[u][v] = min(map[u][v], w);	// Adjacency matrix storage , Keep the minimum distance 
	}
	cout << " Please enter Xiao Ming's location ：" << endl;
	cin >> st;
	Dijkstra(st);
	cout << " Where Xiao Ming is ：" << st << endl;
	for (int i = 1; i <= n; i++)
	{
    
		cout << " Xiao Ming ：" << st << " - " << " Where to go ：" << i << endl;
		if (dist[i] == INF)
			cout << "sorry, There is no way to reach " << endl;
		else
			cout << " The shortest distance is ：" << dist[i] << endl; 
	}
	return 0;
}

If a given graph has a negative weight edge , similar Dijkstra Algorithms and other algorithms are useless ,SPFA Algorithms come in handy . brevity , We agree that weighted digraph G There is no negative weight loop , That is, the shortest path must exist . Using arrays d Record the shortest path estimate of each node , And use adjacency table to store graph G.

bellman-ford Algorithm

Allow negative rings , That is, the edge weight is allowed to be negative .
Only judgment can be made , The weight cannot be calculated .
Relaxation algorithm , Opposite side relaxation ,dijkstra Some inferences of the algorithm .

Find the difference between the maximum value and the minimum value .
You can build constraint diagrams

Realize with adjacency table structure bellman_ford

// Adjacency table structure 
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 0x3f3f3f3f
#define N 1010
int nodenum, edgenum, original; // spot , edge , The starting point 
typedef struct Edge // 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) // Slack （ The order must not be reversed ~）
			{
    
				dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;
				//pre[edge[j].v] = edge[j].u;
			}
	bool flag = 1; // Determine whether there is a negative weight circuit 
	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) // Print the shortest path （ reverse ）
{
    
	while (root != pre[root]) // Forerunner 
	{
    
		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;
}

The adjacency matrix is used to realize bellman_ford

// Adjacency matrix 
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
#define MAX 0x3f3f3f3f
#define N 1010
int nodenum, edgenum, original; // spot , edge , The starting point 
int map[N][N];  // Adjacency matrix 
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; // Set a standard , The smallest is 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++)// This is the cycle of times , Just subtract one from the number of walking 
	{
    
		flag = 1;
		for(int u=1;u<=nodenum;u++)
		if (u != 0)// The starting point is not 
		{
    
			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 << " There are negative circles " << endl;
	}
}
int main()
{
    
	init();
	bellman_ford(0);
	for (int i =0; i <= nodenum; i++)
	{
    
		cout << dis[i] << " ";
	}
	cout << endl;
	return 0;
}

SPFA Algorithm ----Bellman-Ford Algorithm Another name for queue optimization algorithm

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));  // Because it's the longest way , Therefore, it should be initialized to a negative number 
    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) {
     //  Seeking the longest way , Contrary to finding the shortest path 
                dis[v] = dis[u] + w;
                if (!vis[v]) {
    
                    q.push(v);
                    vis[v] = true;
                    ++in[v];
                    if (in[v] > n + 1) {
      // Judge negative loop , Because we added a super source , So follow  n + 1  instead of  n  Compare .
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

Luogu P5960 【 Templates 】 Differential constraint algorithm Answer key

#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;
}

Difference constraint , It's a modeling idea .

That is to model some algebraic constraints into graph theory related problems . Some problems of differential constraints often require high modeling ability in thinking , However, the investigation of specific algorithms is relatively low , So do the problem of differential constraint , Generally, after modeling, it will give people a feeling of fluency and abuse of the problem, hahahaha .

Homework 2770

Still problematic code

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

int n;      //  Altogether N A big camp 
int m;      // It is known that   From i  One camp to the first j At least how many soldiers are there in a battalion 
int c[1001]; //  The first i There are at most C[i] A soldier 
int dist[1001]; // The number of soldiers in the least barracks  a
int S[1001];  // front i  The capacity of a battalion  d
const int mn = 23000;
int ei; // Serial number of the side 
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;  // At the beginning of initialization, the total number of all soldiers is 0
}


bool bellman_ford()
{
    
    int i, k, t;
    for (i = 0; i < n; i++)
    {
    
        /*  Hypothesis number 1 K The starting point of the edge is u ,  The end is v,  Next, consider the following cycle k  Whether the edge will make the source point V0 To v  The shortest distance is shortened  */
        for (k = 0; k < ei; k++)
        {
    
            if (dist[edge[k].start] != mx && dist[edge[k].start] + edge[k].cost < dist[edge[k].end]) // Classical trigonometric formula 
            {
    
                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;// There's a circuit 
    }
    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;  // Construction side <i-1, i>  The number of each barracks is 
            edge[ei].cost = c[i];
            ei++;
            // edge  <i, i-1 >  This weight is 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 */