liuchuo – 第228页

蓝桥杯 ADV-205 算法提高拿糖果（动态规划）

问题描述
妈妈给小B买了N块糖！但是她不允许小B直接吃掉。
　　假设当前有M块糖，小B每次可以拿P块糖，其中P是M的一个不大于根号下M的质因数。这时，妈妈就会在小B拿了P块糖以后再从糖堆里拿走P块糖。然后小B就可以接着拿糖。
　　现在小B希望知道最多可以拿多少糖。
输入格式
　　一个整数N
输出格式
　　最多可以拿多少糖
样例输入
15
样例输出
6
数据规模和约定
N <= 100000

分析：动态规划问题~~首先呢~创建一个满足不大于根号下最大值MAXN的素数表，然后对素数表里面的数逐个遍历~
构建一个dp[i]数组,表示当糖果数量为i的时候所能拿的最多的糖果数量~
对于dp[i]的值：因为小B只能每次拿不大于根号下i的质因数，遍历素数表中满足条件的素数（prime[j] <= sqrt(i) && i % prime[j] == 0），更新dp[i]的值为（dp[i-2*prime[j]] + prime[j]）的最大值~
即：dp[i] = max(dp[i], dp[i-2*prime[j]] + prime[j]);

#include <iostream>
#include <cmath>
using namespace std;
int prime[50000];
int dp[100005];
int book[100005];
int cnt = 0;

void create() {
	int len = sqrt(100005);
    for(int i = 2; i <= len; i++) {
        if(book[i] == 0) {
            prime[cnt++] = i;
            for(int j = i * i; j <= len; j = j + i)
                book[j] = 1;
        }
    }
}

int main() {
    create();
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < cnt; j++) {
            if(prime[j] > sqrt(i))
                break;
            if(i % prime[j] == 0)
                dp[i] = max(dp[i], dp[i-2*prime[j]] + prime[j]);
        }
    }
    cout << dp[n];
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int prime[50000];

int dp[100005];

int book[100005];

int cnt = 0;

void create() {

int len = sqrt(100005);

for(int i = 2; i <= len; i++) {

if(book[i] == 0) {

prime[cnt++] = i;

for(int j = i * i; j <= len; j = j + i)

book[j] = 1;

}

int main() {

create();

int n;

cin >> n;

for(int i = 1; i <= n; i++) {

for(int j = 0; j < cnt; j++) {

if(prime[j] > sqrt(i))

break;

if(i % prime[j] == 0)

dp[i] = max(dp[i], dp[i-2*prime[j]] + prime[j]);

}

cout << dp[n];

return 0;

}

蓝桥杯 ADV-143 算法提高扶老奶奶过街

一共有5个红领巾，编号分别为A、B、C、D、E，老奶奶被他们其中一个扶过了马路。
五个红领巾各自说话：
A ：我和E都没有扶老奶奶
B ：老奶奶是被C和E其中一个扶过大街的
C ：老奶奶是被我和D其中一个扶过大街的
D ：B和C都没有扶老奶奶过街
E ：我没有扶老奶奶
已知五个红领巾中有且只有２个人说的是真话，请问是谁扶这老奶奶过了街？
若有多个答案，在一行中输出，编号之间用空格隔开。
例如
A B C D E（这显然不是正确答案）

分析：建立一个含有5个元素的数组，分别代表abcde五个人。逐个假设abcde是扶老奶奶过街的人，判断他们说话为真的个数是否为2，为2的时候输出

#include <iostream>
using namespace std;
int main() {
	for(int i = 0; i < 5; i++) {
		int a[5] = {0};
		a[i] = 1;
		int sum = 0;
		if(a[0] == 0 && a[4] == 0)
			sum++;
		if(a[2] == 1 || a[4] == 1)
			sum++;
		if(a[2] == 1 || a[3] == 1)
			sum++;
		if(a[1] == 0 && a[2] == 0)
			sum++;
		if(a[4] == 0)
			sum++;
		if(sum == 2)
			cout << (char)('A' + i) << " ";
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

for(int i = 0; i < 5; i++) {

int a[5] = {0};

a[i] = 1;

int sum = 0;

if(a[0] == 0 && a[4] == 0)

sum++;

if(a[2] == 1 || a[4] == 1)

sum++;

if(a[2] == 1 || a[3] == 1)

sum++;

if(a[1] == 0 && a[2] == 0)

sum++;

if(a[4] == 0)

sum++;

if(sum == 2)

cout << (char)('A' + i) << " ";

}

return 0;

}

蓝桥杯 ADV-108 算法提高分数统计

问题描述
　　2016.4.5已更新此题，此前的程序需要重新提交。
问题描述
　　给定一个百分制成绩T，将其划分为如下五个等级之一：
　　90~100为A，80~89为B，70~79为C，60~69为D，0~59为E
　　现在给定一个文件inp，文件中包含若干百分制成绩（成绩个数不超过100），请你统计五个等级段的人数，并找出人数最多的那个等级段，按照从大到小的顺序输出该段中所有人成绩（保证人数最多的等级只有一个）。要求输出到指定文件oup中。
输入格式
　　若干0~100的正整数，用空格隔开
输出格式
　　第一行为5个正整数，分别表示A,B,C,D,E五个等级段的人数
　　第二行一个正整数，表示人数最多的等级段中人数
　　接下来一行若干个用空格隔开的正整数，表示人数最多的那个等级中所有人的分数，按从大到小的顺序输出。
样例输入
100 80 85 77 55 61 82 90 71 60
样例输出
2 3 2 2 1
3
85 82 80
分析：它赖皮。。测试数据里面有分数的个数的值。。而测试样例里面没写。。。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int cmp1(int a, int b) {return a > b; }
int main() {
    vector<vector <int> > v(5);
    int s;
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> s;
        if(s >= 90 && s <= 100) {
            v[0].push_back(s);
        } else if(s >= 80 && s <= 89) {
            v[1].push_back(s);
        } else if(s >= 70 && s <= 79) {
            v[2].push_back(s);
        } else if(s >= 60 && s <= 69) {
            v[3].push_back(s);
        } else {
            v[4].push_back(s);
        }
    }
    int maxn = 0, index = -1;
    for(int i = 0; i < 5; i++) {
        cout << v[i].size() << " ";
        if(v[i].size() > maxn) {
            maxn = v[i].size();
            index = i;
        }
    }
    cout << endl << maxn << endl;
    sort(v[index].begin(), v[index].end(), cmp1);
    for(int i = 0; i < v[index].size(); i++) {
        cout << v[index][i] << " ";
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int cmp1(int a, int b) {return a > b; }

int main() {

vector<vector <int> > v(5);

int s;

int n;

cin >> n;

for(int i = 0; i < n; i++) {

cin >> s;

if(s >= 90 && s <= 100) {

v[0].push_back(s);

} else if(s >= 80 && s <= 89) {

v[1].push_back(s);

} else if(s >= 70 && s <= 79) {

v[2].push_back(s);

} else if(s >= 60 && s <= 69) {

v[3].push_back(s);

} else {

v[4].push_back(s);

}

int maxn = 0, index = -1;

for(int i = 0; i < 5; i++) {

cout << v[i].size() << " ";

if(v[i].size() > maxn) {

maxn = v[i].size();

index = i;

}

cout << endl << maxn << endl;

sort(v[index].begin(), v[index].end(), cmp1);

for(int i = 0; i < v[index].size(); i++) {

cout << v[index][i] << " ";

}

return 0;

}

蓝桥杯 ADV-104 算法提高打水问题

问题描述
　　N个人要打水，有M个水龙头，第i个人打水所需时间为Ti，请安排一个合理的方案使得所有人的等待时间之和尽量小。
输入格式
　　第一行两个正整数N M 接下来一行N个正整数Ti。
　　N,M<=1000，Ti<=1000
输出格式
　　最小的等待时间之和。（不需要输出具体的安排方案）
样例输入
7 3
3 6 1 4 2 5 7
样例输出
11
提示
　　一种最佳打水方案是，将N个人按照Ti从小到大的顺序依次分配到M个龙头打水。
　　例如样例中，Ti从小到大排序为1，2，3，4，5，6，7，将他们依次分配到3个龙头，则去龙头一打水的为1，4，7；去龙头二打水的为2,5；去第三个龙头打水的为3,6。
　　第一个龙头打水的人总等待时间 = 0 + 1 + (1 + 4) = 6
　　第二个龙头打水的人总等待时间 = 0 + 2 = 2
　　第三个龙头打水的人总等待时间 = 0 + 3 = 3
　　所以总的等待时间 = 6 + 2 + 3 = 11

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
    int n, r;
    scanf("%d %d", &n, &r);
    int *a = new int[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a+n);
    int ans = 0;
    int cnt = n / r;
    while(cnt--) {
        for(int j = 0; j < cnt * r; j++)
            ans += a[j];
    }
    for(int i = n/r*r; i < n; i++) {
        for(int j = i % r; j < n/r*r; j += r)
            ans += a[j];
    }
    cout << ans;
    delete [] a;
    return 0;
}

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

int main() {

int n, r;

scanf("%d %d", &n, &r);

int *a = new int[n];

for(int i = 0; i < n; i++) {

scanf("%d", &a[i]);

}

sort(a, a+n);

int ans = 0;

int cnt = n / r;

while(cnt--) {

for(int j = 0; j < cnt * r; j++)

ans += a[j];

}

for(int i = n/r*r; i < n; i++) {

for(int j = i % r; j < n/r*r; j += r)

ans += a[j];

}

cout << ans;

delete [] a;

return 0;

}

蓝桥杯 ADV-83 算法提高寻找三位数

问题描述
　　将1，2，…，9共9个数分成三组，分别组成三个三位数，且使这三个三位数构成
　　1：2：3的比例，试求出所有满足条件的三个三位数。
　　例如：三个三位数192，384，576满足以上条件。
输入格式
　　无输入文件
输出格式
　　输出每行有三个数，为满足题设三位数。各行为满足要求的不同解。
分析：先确定第一个数字，然后判断这个数字的两倍数和三倍数是否满足条件~用book数组标记当前数字是否已经出现过~

#include <iostream>
using namespace std;
bool judge(int i, int j, int k) {
    int book[10] = {0};
    book[0] = 1;
    if(i == j || j == k || i == k)
        return false;
    book[i] = 1, book[j] = 1, book[k] = 1;
    int one = i * 100 + j * 10 + k;
    int two = 2 * one;
    int three = 3 * one;
    if(two >= 666 || three >=987)
        return false;
    if(book[two/100] == 1)
        return false;
    else
        book[two/100] = 1;
    
    if(book[two%100/10] == 1)
        return false;
    else
        book[two%100/10] = 1;
    
    if(book[two%10] == 1)
        return false;
    else
        book[two%10] = 1;
    
    if(book[three/100] == 1)
        return false;
    else
        book[three/100] = 1;
    
    if(book[three%100/10] == 1)
        return false;
    else
        book[three%100/10] = 1;
    
    if(book[three%10] == 1)
        return false;
    else
        return true;
}
int main() {
    for(int i = 1; i <= 3; i++) {
        for(int j = 1; j <= 9; j++) {
            for(int k = 1; k <= 9; k++) {
                if(judge(i, j, k) == true) {
                    int one = i * 100 + j * 10 + k;
                    cout << one << " " << one * 2 << " " << one * 3 << endl;
                }
            }
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

bool judge(int i, int j, int k) {

int book[10] = {0};

book[0] = 1;

if(i == j || j == k || i == k)

return false;

book[i] = 1, book[j] = 1, book[k] = 1;

int one = i * 100 + j * 10 + k;

int two = 2 * one;

int three = 3 * one;

if(two >= 666 || three >=987)

return false;

if(book[two/100] == 1)

return false;

else

book[two/100] = 1;

if(book[two%100/10] == 1)

return false;

else

book[two%100/10] = 1;

if(book[two%10] == 1)

return false;

else

book[two%10] = 1;

if(book[three/100] == 1)

return false;

else

book[three/100] = 1;

if(book[three%100/10] == 1)

return false;

else

book[three%100/10] = 1;

if(book[three%10] == 1)

return false;

else

return true;

}

int main() {

for(int i = 1; i <= 3; i++) {

for(int j = 1; j <= 9; j++) {

for(int k = 1; k <= 9; k++) {

if(judge(i, j, k) == true) {

int one = i * 100 + j * 10 + k;

cout << one << " " << one * 2 << " " << one * 3 << endl;

}

return 0;

}

【最短路径】：Dijkstra算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法

求最短路径最常用的算法有：
Dijkstra算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法。
Dijkstra算法、SPFA算法、Bellman-Ford算法这三个求单源最短路径，最后一个Floyd-Warshall算法可以求全局最短路径也可以求单源路径，效率比较低。
SPFA算法是Bellman算法的队列优化。
Dijkstra算法不能求带负权边的最短路径，而SPFA算法、Bellman-Ford算法、Floyd-Warshall可以求带负权边的最短路径。
Bellman-Ford算法的核心代码只有4行，Floyd-Warshall算法的核心代码只有5行。

1.最基本的求单源最短路径方法是图的深度优先遍历：
用 min = 99999999 记录路径的最小值，book[i]标记结点 i 是否被访问过~

#include <iostream>
using namespace std;
int minn = 99999999;
int book[101];
int n;
int e[101][101];

//cur是当前所在的城市编号，dis是当前已经走过的路程
void dfs(int cur, int dis) {
    if (dis > minn)
        return ;
    if (cur == n) {
        if (dis < minn)
            minn = dis;
        return ;
    }
    for (int i = 1; i <= n; i++) {//从cur到所有结点依次尝试
        if (e[cur][i] != 99999999 && book[i] == 0) {
            book[i] = 1;
            dfs(i, dis + e[cur][i]);//从i结点出发到其他所有结点依次尝试直到遇到要求的n结点为止
            book[i] = 0;
        }
    }
    return ;
}

int main() {
    int m;
    cin >> n >> m;
    int a, b, c;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j)
                e[i][j] = 0;
            else
                e[i][j] = 99999999;
        }
    }
    for(int i = 1; i <= m; i++) {
        cin >> a >> b >> c;
        e[a][b] = c;
    }
    book[1] = 1;
    dfs(1, 0);
    cout << minn;
    return 0;
}

#include <iostream>

using namespace std;

int minn = 99999999;

int book[101];

int n;

int e[101][101];

//cur是当前所在的城市编号，dis是当前已经走过的路程

void dfs(int cur, int dis) {

if (dis > minn)

return ;

if (cur == n) {

if (dis < minn)

minn = dis;

return ;

}

for (int i = 1; i <= n; i++) {//从cur到所有结点依次尝试

if (e[cur][i] != 99999999 && book[i] == 0) {

book[i] = 1;

dfs(i, dis + e[cur][i]);//从i结点出发到其他所有结点依次尝试直到遇到要求的n结点为止

book[i] = 0;

}

return ;

}

int main() {

int m;

cin >> n >> m;

int a, b, c;

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= n; j++) {

if (i == j)

e[i][j] = 0;

else

e[i][j] = 99999999;

}

for(int i = 1; i <= m; i++) {

cin >> a >> b >> c;

e[a][b] = c;

}

book[1] = 1;

dfs(1, 0);

cout << minn;

return 0;

}

2.单源最短路径：Dijkstra算法
dis[i]是需要不断更新的数组，它表示当前结点1(源点)到其余各结点的最短路径长度~
book[i]标记当前结点最短路径是确定值还是估计值~
算法实现的过程是：每次找到离结点1最近的那个点，然后以该结点为中心扩展，最终得到源点到所有点的最短路径~~每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质~~
找到所有估计值当中最小的值min以及它的结点u，然后把该结点u标记为确定值，通过这个确定值为中转点更新别的所有值的最短路径(松弛别的两个顶点连接的边)

//邻接矩阵
int n, e[maxv][maxv];
int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点
bool vis[maxv] = {false};
void Dijkstra(int s) {
  fill(dis, dis + maxv, inf);
  dis[s] = 0;
  for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身
  for(int i = 0; i < n; i++) {
    int u = -1, minn = inf;
    for(int j = 0; j < n; j++) {
      if(visit[j] == false && dis[j] < minn) {
        u = j;
        minn = dis[j];
      }
    }
    if(u == -1) return;
    visit[u] = true;
    for(int v = 0; v < n; v++) {
      if(visit[v] == false && e[u][v] != inf && dis[u] + e[u][v] < dis[v]) {
        dis[v] = dis[u] + e[u][v];
        pre[v] = u; // pre用来标注当前结点的前一个结点
      }
    }
  }
}

//邻接矩阵

int n, e[maxv][maxv];

int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点

bool vis[maxv] = {false};

void Dijkstra(int s) {

fill(dis, dis + maxv, inf);

dis[s] = 0;

for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身

for(int i = 0; i < n; i++) {

int u = -1, minn = inf;

for(int j = 0; j < n; j++) {

if(visit[j] == false && dis[j] < minn) {

u = j;

minn = dis[j];

}

if(u == -1) return;

visit[u] = true;

for(int v = 0; v < n; v++) {

if(visit[v] == false && e[u][v] != inf && dis[u] + e[u][v] < dis[v]) {

dis[v] = dis[u] + e[u][v];

pre[v] = u; // pre用来标注当前结点的前一个结点

}

//邻接表
struct node {
  int v, dis;
}
vector<node> e[maxv];
int n;
int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点
bool vis[maxv] = {false};
for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身
void Dijkstra(int s) {
  fill(d, d + maxv, inf);
  dis[s] = 0;
  for(int i = 0; i < n; i++) {
    int u = -1, minn = inf;
    for(int j = 0; j < n; j++) {
      if(visit[j] == false && dis[j] < minn) {
        u = j;
        minn = dis[j];
      }
    }
    if(u == -1) return ;
    visit[u] = true;
    for(int j = 0; j < e[u].size(); j++) {
      int v = e[u][j].v;
      if(visit[v] == false && dis[u] + e[u][j].dis < dis[v]) {
        dis[v] = dis[u] + e[u][j].dis;
        pre[v] = u;
      }
    }
  }
}

//邻接表

struct node {

int v, dis;

}

vector<node> e[maxv];

int n;

int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点

bool vis[maxv] = {false};

for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身

void Dijkstra(int s) {

fill(d, d + maxv, inf);

dis[s] = 0;

for(int i = 0; i < n; i++) {

int u = -1, minn = inf;

for(int j = 0; j < n; j++) {

if(visit[j] == false && dis[j] < minn) {

u = j;

minn = dis[j];

}

if(u == -1) return ;

visit[u] = true;

for(int j = 0; j < e[u].size(); j++) {

int v = e[u][j].v;

if(visit[v] == false && dis[u] + e[u][j].dis < dis[v]) {

dis[v] = dis[u] + e[u][j].dis;

pre[v] = u;

}

3.Bellman-Ford算法——解决负权边
算法思想：对所有的边进行n-1次“松弛”操作

核心算法四行：
for (k = 1; k <= n - 1; k++)
    for (i = 1; i <= m; i++)
        if (dis[v[i]] > dis[u[i]] + w[i])
            dis[v[i]] = dis[u[i]] + w[i];
进行n-1轮的原因：在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1边。

//检验负权回路
如果在进行最短路径算法后，仍然有可以松弛的边，那么就是存在负权回路
flag = 0;
for (i = 1; i <= m; i++)
    if (dis[v[i]] > dis[u[i]] + w[i])
        flag = 1;
if (flag == 1)
    printf("此图含有负权回路");

核心算法四行：

for (k = 1; k <= n - 1; k++)

for (i = 1; i <= m; i++)

if (dis[v[i]] > dis[u[i]] + w[i])

dis[v[i]] = dis[u[i]] + w[i];

进行n-1轮的原因：在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1边。

//检验负权回路

如果在进行最短路径算法后，仍然有可以松弛的边，那么就是存在负权回路

flag = 0;

for (i = 1; i <= m; i++)

if (dis[v[i]] > dis[u[i]] + w[i])

flag = 1;

if (flag == 1)

printf("此图含有负权回路");

如果在新一轮的松弛中数组dis没有发生变化，则可以提前跳出循环
#include <iostream>
#include <cstdio>
//n个结点，m条边
using namespace std;
int main() {
    int dis[10], bak[10], n, m, u[10], v[10], w[10], check, flag;
    int inf = 99999999;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d %d %d", &u[i], &v[i], &w[i]);
    
    for (int i = 1; i <= n; i++)
        dis[i] = inf;
    dis[1] = 0;
    
    for (int k = 1; k <= n - 1; k++) {
        for (int i = 1; i <= n; i++)
            bak[i] = dis[i];//将dis数组备份入bak数组中，为了下面的检查是否更新而进行剪枝
        for (int i = 1; i <= m; i++)
            if (dis[v[i]] > dis[u[i]] + w[i])
                dis[v[i]] = dis[u[i]] + w[i];
        check = 0;
        for (int i = 1; i < n; i++)
            if (bak[i] != dis[i]) {
                check = 1;
                break;
            }
        // 如果对于所有的结点，dis的值都没有被更新，那就提前跳出循环，说明不需要进行n-1次了
        if (check == 0)
            break;
    }
    //检查是否含有负权回路（可省略）
    flag = 0;
    for (int i = 1; i <= m; i++)
        if (dis[v[i]] > dis[u[i]] + w[i])
            flag = 1;
    if (flag == 1)
        printf("此图含有负权回路");
    else {
        for (int i = 1; i <= n; i++) 
            printf("%d ", dis[i]);
    }
    return 0;
}

如果在新一轮的松弛中数组dis没有发生变化，则可以提前跳出循环

#include <iostream>

#include <cstdio>

//n个结点，m条边

using namespace std;

int main() {

int dis[10], bak[10], n, m, u[10], v[10], w[10], check, flag;

int inf = 99999999;

scanf("%d %d", &n, &m);

for (int i = 1; i <= m; i++)

scanf("%d %d %d", &u[i], &v[i], &w[i]);

for (int i = 1; i <= n; i++)

dis[i] = inf;

dis[1] = 0;

for (int k = 1; k <= n - 1; k++) {

for (int i = 1; i <= n; i++)

bak[i] = dis[i];//将dis数组备份入bak数组中，为了下面的检查是否更新而进行剪枝

for (int i = 1; i <= m; i++)

if (dis[v[i]] > dis[u[i]] + w[i])

dis[v[i]] = dis[u[i]] + w[i];

check = 0;

for (int i = 1; i < n; i++)

if (bak[i] != dis[i]) {

check = 1;

break;

}

// 如果对于所有的结点，dis的值都没有被更新，那就提前跳出循环，说明不需要进行n-1次了

if (check == 0)

break;

}

//检查是否含有负权回路（可省略）

flag = 0;

for (int i = 1; i <= m; i++)

if (dis[v[i]] > dis[u[i]] + w[i])

flag = 1;

if (flag == 1)

printf("此图含有负权回路");

else {

for (int i = 1; i <= n; i++)

printf("%d ", dis[i]);

}

return 0;

}

4.Bellman-Ford的队列优化(SPFA算法)
每次选取首顶点u，对u的所有出边进行松弛操作~如果有一条u->v的边，通过这条边使得源点到顶点v的路程变短，且顶点v不在当前队列中，就把这个顶点v放入队尾。同一个顶点在队列中出现多次是毫无意义的，所以用一个数组来判重复，判断哪些点已经在队列中。对顶点u的所有出边都松弛完毕后，就将顶点v出队~

#include <iostream>
#include <cstdio>
using namespace std;
int main() {
    int n, m;
    int u[8], v[8], w[8];
    int first[6], next[8];
    int dis[6] = {0}, book[6] = {0};
    int que[101] = {0};
    int head = 1;
    int tail = 1;
    int inf = 99999999;
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; i++)
        dis[i] = inf;
    dis[1] = 0;
    
    for (int i = 1; i <= n; i++)
        book[i] = 0;
    
    for (int i = 1; i <= n; i++)
        first[i] = -1;
    
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &u[i], &v[i], &w[i]);
        next[i] = first[u[i]];
        first[u[i]] = i;
    }
    
    que[tail] = 1;
    tail++;
    book[1] = 1;
    
    int k;
    while (head < tail) {
        k = first[que[head]];
        while (k != -1) {
            if (dis[v[k]] > dis[u[k]] + w[k]) {
                dis[v[k]] = dis[u[k]] + w[k];
                if (book[v[k]] == 0) {
                    que[tail] = v[k];
                    tail++;
                    book[v[k]] = 1;
                }
            }
            k = next[k];
        }
        book[que[head]] = 0;
        head++;
    }
    
    for (int i = 1; i <= n; i++)
        printf("%d ", dis[i]);
    return 0;
}

#include <iostream>

#include <cstdio>

using namespace std;

int main() {

int n, m;

int u[8], v[8], w[8];

int first[6], next[8];

int dis[6] = {0}, book[6] = {0};

int que[101] = {0};

int head = 1;

int tail = 1;

int inf = 99999999;

scanf("%d %d", &n, &m);

for (int i = 1; i <= n; i++)

dis[i] = inf;

dis[1] = 0;

for (int i = 1; i <= n; i++)

book[i] = 0;

for (int i = 1; i <= n; i++)

first[i] = -1;

for (int i = 1; i <= m; i++) {

scanf("%d %d %d", &u[i], &v[i], &w[i]);

next[i] = first[u[i]];

first[u[i]] = i;

}

que[tail] = 1;

tail++;

book[1] = 1;

int k;

while (head < tail) {

k = first[que[head]];

while (k != -1) {

if (dis[v[k]] > dis[u[k]] + w[k]) {

dis[v[k]] = dis[u[k]] + w[k];

if (book[v[k]] == 0) {

que[tail] = v[k];

tail++;

book[v[k]] = 1;

}

k = next[k];

}

book[que[head]] = 0;

head++;

}

for (int i = 1; i <= n; i++)

printf("%d ", dis[i]);

return 0;

}