第五章.图论

图的概念

 子图：

生成子图：全部的顶点

 图的存储

邻接矩阵

#include <iostream>

#include <cstring>

using namespace std;

const int N = 1010;

int n, m;

int edges[N][N];

int main()
{
 memset(edges, -1, sizeof edges);
 cin >> n >> m; // 读⼊结点个数以及边的个数 
 for(int i = 1; i <= m; i++)
 {
 int a, b, c; cin >> a >> b >> c; 
 // a - b 有⼀条边，权值为 c 
 edges[a][b] = c;
 // 如果是⽆向边，需要反过来再存⼀下 
 edges[b][a] = c;
 }
return 0;
}

邻接表 

和树的存储⼀模⼀样，只不过如果存在边权的话，我们的vector数组⾥⾯放⼀个结构体或者是pair即 可。  

#include <iostream>

#include <vector>

using namespace std;

typedef pair<int, int> PII;//那个结点，权值

const int N = 1e5 + 10;

int n, m;
vector<PII> edges[N];

int main()
{
 cin >> n >> m; // 读⼊结点个数以及边的个数 
 for(int i = 1; i <= m; i++)
 {
 int a, b, c; cin >> a >> b >> c;
 // a 和 b 之间有⼀条边，权值为 c 
 edges[a].push_back({b, c});
 
 // 如果是⽆向边，需要反过来再存⼀下 
 edges[b].push_back({a, c});
 }
 return 0;
}

 链式前向星

和树的存储⼀模⼀样，只不过如果存在边权的话，我们多创建⼀维数组，⽤来存储边的权值即可。

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

// 链式前向星 

int h[N], e[N * 2], ne[N * 2], w[N * 2], id;

int n, m;

// 其实就是把 b 头插到 a 所在的链表后⾯ 

void add(int a, int b, int c)
{
 id++;
 e[id] = b;
 w[id] = c; // 多存⼀个权值信息 
 ne[id] = h[a];
 h[a] = id;
}

int main()
{
 cin >> n >> m; // 读⼊结点个数以及边的个数 
 for(int i = 1; i <= m; i++)
 {
 int a, b, c; cin >> a >> b >> c;
 // a 和 b 之间有⼀条边，权值为 c 
 add(a, b, c); add(b, a, c);
 }
 return 0;
}

 图的遍历

dfs

bfs 

最小生成树 （无向无环图）

概念

1.Prim算法 P3366 【模板】最小生成树 - 洛谷

邻接矩阵实现 

#include<iostream>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 5e3 + 10;
int dis[N]; //记录每个结点到其他结点的巨鹿
bool st[N];//记录每个节点是否被遍历过

int edge[N][N];//记录每个结点到其他结点的巨鹿

int n, m;

//prim算法实现
int prim()
{
	//把dis初始化成无穷大
	memset(dis, INF, sizeof(dis));
	dis[1] = 0;//第一个结点开头

	int ret = 0;
	for (int i = 1; i <= n; i++)
	{
		int t = 0;
		//找最近点
		for (int j = 1; j <= n; j++)
		{
			if (!st[j] && dis[j] < dis[t])t = j;//更新最小值的下标
		}
		//判断是否联通
		if (dis[t] == INF)return INF;
		//把该点加进去
		st[t] = true;
		ret += dis[t];
		//更新dis
		for (int i = 1; i <= n; i++)
		{
			if (dis[i] > edge[t][i])//如果距离大于新的结点距离其他节点的距离，更新
				dis[i] = edge[t][i];
		}
	}
	return ret;
}

int main()
{
	cin >> n >> m;
	memset(edge, INF, sizeof(edge));
	for (int i = 1; i <= m; i++)
	{
		int x, y, z; cin >> x >> y >> z;
		//注意有重边的情况，注意是取笑，初始化为无穷大
		edge[x][y] = edge[y][x] = min(edge[x][y], z);
	}
	int ret = prim();
	if (ret == INF)cout << "orz" << endl;
	else
		cout << ret << endl;
}

 vector数组实现

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

typedef pair<int, int> PII;//连接的点，权值
const int INF = 0x3f3f3f3f;
const int N = 5e3 + 10;

int n, m;
int dis[N];
bool st[N];
vector<PII> dp[N];

int prim()
{
	memset(dis, INF, sizeof(dis));
	dis[1] = 0;
	int ret = 0;

	for (int i = 1; i <= n; i++)//加入n个点，功德圆满
	{
		//找最近的点
		int t = 0;//dis[0]给初始化成INF了
		for (int j = 1; j<= n; j++)
		{
			if (!st[j] && dis[j] < dis[t])//没有被访问过并且比t小，更新t
			{
				t = j;
			}
		}
		//判断是否联通
		if (dis[t] == INF)return INF;
		st[t] = true;
		ret += dis[t];
		//更新dis
		for (auto& x : dp[t])
		{
			int a = x.first;//相连的点
			int b = x.second;//相连的点的权值
			/*if (dis[a] > b)dis[a] = b;*/
			dis[a] = min(dis[a], b);//这里可以解决重边的情况
		}
	}
	return ret;
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, z; cin >> x >> y >> z;
		dp[x].push_back({ y,z });
		dp[y].push_back({ x,z });
	}
	int ret = prim();
	if (ret == INF)cout << "orz" << endl;
	else
		cout << ret << endl;
}

2.克鲁斯卡尔算法（并查集实现）

P3366 【模板】最小生成树 - 洛谷

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 5010;//点
const int M = 2e5 + 10;//边
const int INF = 0x3f3f3f3f;

struct node
{
	int x, y, z;
}a[M];

int f[N];//并查集
int n, m;

int find(int x)
{
	return f[x] == x ? x : f[x] = find(f[x]);
}
void un(int x, int y)
{
	f[find(x)] = find(y);
}

bool cmp(node& x, node& y)
{
	return x.z < y.z;
}

int kruskal()
{
	int ret = 0;
	int cnt = 0;
	for (int i = 1; i <= m; i++)
	{
		int x = a[i].x, y = a[i].y, z = a[i].z;
		if (find(x) != find(y))//没有并在一起，就整
		{
			cnt++;//记录边的个数，最小生成树，节点数n，边数n-1
			ret += z;
			un(x, y);
		}
	}
	if (cnt != n-1)return INF;//成功的话是n - 1,没有说明不联通
	return ret;
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> a[i].x >> a[i].y >> a[i].z;
	}
	//并查集初始化
	for (int i = 1; i <= n; i++)f[i] = i;
	//排序，从小到大
	sort(a + 1, a + 1 + m, cmp);
	int ret = kruskal();
	if (ret == INF)cout << "orz" << endl;
	else
		cout << ret << endl;
}

P1194 买礼物 - 洛谷

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 500*500+10;//结点*结点 == 边的个数，我们存的是边的个数
const int M = 1010;
int a, n;//A和节点数
int pos;//有几条边要存
int f[N];//并查集

struct node
{
	int x, y, z;
}b[N];//存边之间的个数

bool cmp(node& x, node& y)//排序
{
	return x.z < y.z;
}

int find(int x)
{
	return f[x] == x ? x : f[x] = find(f[x]);
}
//克鲁斯卡尔算法
int kk()
{
	int ret = 0;//总价
	int cnt = 0;//几条边，用来计算分成几块，有几块就*多少个A
	for (int i = 1; i <= pos; i++)
	{
		int x = b[i].x, y = b[i].y, z = b[i].z;//取出边的数据
		int fx = find(x);
		int fy = find(y);
		if (fx != fy && z < a && z != 0)
		{
			ret += z;
			cnt++;//计算有多少条边
			f[find(x)] = find(y);//合并
		}
	}
	ret += (n - cnt) * a;//有几块树
	return ret;
}

int main()
{
	cin >> a >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			int k; cin >> k;
			//只需要存一条边的关系
            //但其实就算不要也无所谓，因为并查集合并后，也不会要重复的
            //克鲁斯卡尔算法只需要存取，边的数据就好了，不重复更好
			if (i >= j)continue;
			pos++;
			b[pos].x = i, b[pos].y = j, b[pos].z = k;
		}
	}
	for (int i = 1; i <= n; i++)f[i] = i;

	sort(b + 1, b + 1 + pos,cmp);

	int ret = kk();
	cout << ret << endl;
}

P2330 [SCOI2005] 繁忙的都市 - 洛谷

瓶颈树：生成所有生成树中，最大边权值最小的那棵树。

也就是最小生成树。

最小生成树的最大边值也就是最终结果

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 310;
const int M = 8010;
int n, m;
int pos;
int f[N];

struct node
{
	int x, y, z;
}a[M];

int find(int x)
{
	return f[x] == x ? x : f[x] = find(f[x]);
}

bool cmp(node& x, node& y)
{
	return x.z < y.z;
}

int ret = 0;
void kk()
{
	for (int i = 1; i <= m; i++)
	{
		int x = a[i].x, y = a[i].y, z = a[i].z;
		int fx = find(x), fy = find(y);
		if (fx != fy)
		{
			ret = max(ret, z);
			f[fx] = fy;
		}
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;
		a[i].x = x, a[i].y = y, a[i].z = z;
	}
	cout << n - 1 << " ";
	for (int i = 1; i <= n; i++)f[i] = i;
	sort(a + 1, a + 1 + m, cmp);
	kk();
	cout << ret << endl;
}

P2573 [SCOI2012] 滑雪 - 洛谷

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef long long LL;

const int N = 1e5 + 10;
const int M = 2e6 + 10;//考虑两重变

typedef pair<int, int> PII;//可以到的点，到该点的距离

int n, m;//n个景点，m条边
int h[N];//每个景点的高度

vector<PII> dp[N];//记录该点可以去的所有的点+到的距离

bool st[N];
LL cnt;//记录有多少个景点被访问了
int pos;//记录有多少条边

struct node
{
	int x, y, z;
}a[M];//记录边的数据

int f[N];//并查集

void dfs(int u)//找所有可以到达的边
{
	cnt++;
	st[u] = true;
	for (auto& s : dp[u])//遍历该点可以到达的每一条边，并且进行记录
	{
		int x = s.first, y = s.second;
		++pos;//多一条边
		a[pos].x = u, a[pos].y = x, a[pos].z = y;
		if (!st[x])//没有被访问过
		{
			dfs(x);
		}
	}
}
bool cmp(node& x, node& y)//从该点到宁一个点的高的优先，其次是距离
{
	int x1 = x.x, y1 = x.y, z1 = x.z;
	int x2 = y.x, y2 = y.y, z2 = y.z;
	if (h[y1] != h[y2])return h[y1] > h[y2];
	return z1 < z2;
}

int find(int x)
{
	return f[x] == x ? x : f[x] = find(f[x]);
}

LL ret;
void kk()
{
	sort(a + 1, a + 1 + pos, cmp);
	for (int i = 1; i <= n; i++)f[i] = i;

	for (int i = 1; i <= pos; i++)
	{
		int x = a[i].x, y = a[i].y, z = a[i].z;
		int fx = find(x);
		int fy = find(y);
		if (fx != fy)
		{
			ret += z;
			f[fx] = fy;
		}
	}

}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)cin >> h[i];

	for (int i = 1; i <= m; i++)
	{
		int x, y, z; cin >> x >> y >> z;
		if (h[x] >= h[y])dp[x].push_back({ y,z });
		if (h[y] >= h[x])dp[y].push_back({ x,z });//如果是 == 的话，那么两边的都要记录
	}
	dfs(1);
	
	kk();
	cout << cnt << " "<<ret << endl;
}

有向图：

由于克鲁斯卡尔算法要把所有的边进行排序没所以我们要创建一个起点,终点，边的结构体

题目没有明确给出那就自己创建。

dfs:把所有的路径都找到。（遍历到一条边就加入路径）
用胶囊把所有可以到的点统计到。->生成最小生成树。

最小生成树：利用dfs找到的路径据生成最小生成树
距离最短->所有距离的总和。--->最小生成树。

选边的时候，优先去往高的位置的边，其次才是距离

拓扑排序 （有向无环图）

概念：

拓扑排序

AOV网

实现

 代码实现B3644 【模板】拓扑排序 / 家谱树 - 洛谷

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

const int N = 110;
vector<int> edge[N];//把后代进行拖尾
int in[N];//记录自己的前辈有多少个

int main()
{
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int j;
		while (cin >> j, j)
		{
			edge[i].push_back(j);//把后代接在后面
			in[j]++;//后代的前辈+1
		}
	}
	queue<int> q;
	for (int i = 1; i <= n; i++)//把没有前辈的加进队列
	{
		if (in[i] == 0)q.push(i);
	}
	while (q.size())
	{
		auto x = q.front(); q.pop();
		cout << x << " ";
		for (auto s : edge[x])//前辈没了，该前辈的后代的前辈-1
		{
			in[s]--;
			if (in[s] == 0)q.push(s);//后代变成0，加进队列
		}
	}
	return 0;
}

 P2712 摄像头 - 洛谷

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

const int N = 510;//摄像头位置可以到500
vector<int> edge[N];//记录后面的
int in[N];//标记前面的
bool st[N];//标记要砸坏的摄像头

int main()
{
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int x, y;
		cin >> x >> y;//位置  可以看多少个
		st[x] = true;//标记
		for (int i = 1; i <= y; i++)
		{
			int ch; cin >> ch;
			edge[x].push_back(ch);
			in[ch]++;
		}
	}
	//进队列
	queue<int> q;
	for (int i = 0; i <= 500; i++)
	{
		if (st[i] && in[i] == 0)q.push(i);
	}

	while (q.size())
	{
		int x = q.front(); q.pop();
		for (auto& ch : edge[x])
		{
			in[ch]--;
			if (in[ch] == 0)q.push(ch);
		}
	}
	int ret = 0;
	for (int i = 0; i <= 500; i++)
	{
		if (st[i] && in[i] != 0)ret++;
	}
	if (ret == 0)cout << "YES" << endl;
	else cout << ret << endl;
}

加了一个标记要砸坏的bool st[]

进队列：是餐厅里的摄像头，并且没有前辈

记录ret:是餐厅里的摄像头，in不为0

 P4017 最大食物链计数 - 洛谷

//路径类dp动态规划 + 拓扑排序填表
#include<iostream>
#include<queue>
#include<vector>
using namespace std;

const int N = 5010;
const int MOD = 80112002;

int n, m;
vector<int> edge[N];//记录拖尾
int in[N];//记录前驱
int out[N];//找最大捕食者
int f[N];//从起点到i位置的路径条数，处理不同块之间的情况

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y; cin >> x >> y;
		edge[x].push_back(y);//记录后者
		in[y]++; out[x]++;//后者的前辈+1，前者的后背+1
	}
	queue<int> q;
	//进队列
	for (int i = 1; i <= n; i++)
	{
		if (in[i] == 0)//没有前者就给我进队列
		{
			f[i] = 1;//第一只的f[i]进行初始化为1
			q.push(i);
		}
	}
	while (q.size())
	{
		int x = q.front(); q.pop();
		for (auto& ch : edge[x])//遍历后辈
		{
			f[ch] =(f[ch] + f[x])%MOD;//当前的+前辈的
			in[ch]--;//前辈--
			if (in[ch] == 0)q.push(ch);//为0 干进队列
		}
	}
	int ret = 0;
	//怎么找最大捕食者？找出度为0的数字
	for (int i = 1; i <= n; i++)
	{
		if (out[i] == 0)
			ret = (ret+f[i])%MOD;
	}
	cout << ret << endl;
	return 0;
}

 P1113 杂务 - 洛谷

拿最大的进行更新，因为大的做完了，小的也就做完了。

 最短时间，所有情况下，取最大值。

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

const int N = 1e4 + 10;
vector<int> edge[N];//记录拖尾
int f[N];//记录到i下标的最小值
int in[N];//记录前面有几个
int len[N];//记录工作完需要的时间

int n;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int x, a; cin >> x >> len[i];
		while (cin >> a, a)
		{
			edge[x].push_back(a);
			in[a]++;
		}
	}
	//进队列
	queue<int> q;
	for (int i = 1; i <= n; i++)
	{
		if (in[i] == 0)q.push(i);
	}
	int ret = 0;
	while (q.size())
	{
		int x = q.front(); q.pop();
		f[x] += len[x];
		ret = max(ret, f[x]);
		for (auto& ch : edge[x])
		{
			f[ch] = max(f[ch], f[x]);//一个一个遍历更新出最大的。具体还是看解题思路吧
			in[ch]--;
			if (in[ch] == 0)q.push(ch);
		}
	}
	cout << ret << endl;
	return 0;
}

单源最短路

概念

 dijkstra实现（解决不了负权值）

 P3371 【模板】单源最短路径（弱化版） - 洛谷

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

typedef pair<int, int> PII;
const int N = 1e4 + 10;
const int INF = 2147483647;
vector<PII> edge[N];//i后面接的点j，和到j的距离
bool st[N];//是否已经确定是最优解
int dist[N];//起点到个点的最小值
int n, m, s;

void dijksta()
{
	for (int i = 1; i < n; i++)
	{
		int a = 0;
		for (int i = 1; i <= n; i++)//找目前dist中的最小值
		{
			if (!st[i] && dist[i] < dist[a])a = i;//没有被确定最优，且最小
		}
		st[a] = true;
		for (auto& ch : edge[a])//更新：松弛操作
		{
			int v = ch.first, w = ch.second;
			if (dist[v] > dist[a] + w)
			{
				dist[v] = dist[a] + w;
			}
		}
	}
	for (int i = 1; i <= n; i++)cout << dist[i] << " ";
}

int main()
{

	cin >> n >> m >> s;
	for (int i = 1; i <= m; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;
		edge[x].push_back({ y,z });
	}
	for (int i = 0; i <= n; i++)dist[i] = INF;//如果要初始化的数字太大，那就用不了memset
	dist[s] = 0;//初始化起点
	dijksta();
	return 0;
}

P4779 【模板】单源最短路径（标准版） - 洛谷

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>

using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;

int n, m,s;
vector<PII> edge[N];
bool st[N];
int dis[N];
priority_queue<PII,vector<PII>,greater<PII>> q;

void dijkstra()
{
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	q.push({ 0,s });//先存距离，后存结点，因为，greater会根据第一个数据first进行小跟堆排序
	while (q.size())
	{
		auto t = q.top(); q.pop();
		int a = t.second;
		if (st[a])continue;
		st[a] = true;
		for (auto& x : edge[a])
		{
			int b = x.first, c = x.second;
			if (dis[a] + c < dis[b])
			{
				dis[b] = dis[a] + c;
				q.push({ dis[b], b });
			}
		}
	}
	for (int i = 1; i <= n; i++)cout << dis[i] << " ";
}

int main()
{
	cin >> n >> m>>s;
	for (int i = 1; i <= m; i++)
	{
		int a, b, c; cin >> a >> b >> c;
		edge[a].push_back({ b,c });
	}
	dijkstra();
	return 0;
}

BF算法（）可以解决负权以及最短路不存在的情况（负环）

负环：每次转一圈，权值就减小

P3371 【模板】单源最短路径（弱化版） - 洛谷

#include<iostream>
#include<vector>

using namespace std;
const int N = 1e4 + 10;
const int INF = 2147483647;

typedef pair<int, int> PII;
vector<PII> edge[N];
int dis[N];
int n, m , s;

void BF()
{
	for (int i = 1; i <= n; i++)dis[i] = INF;
	dis[s] = 0;
	for (int i = 1; i < n; i++)//n-1条边，那就n-1次就好
	{
		bool judge = false;//没有了松弛操作，就退出
		for (int j = 1; j <= n; j++)//遍历全部
		{
			if (dis[j] == INF)continue;//if (dis[j] + b < dis[a]),这一步+，会让超出int范围变成负数，
			for (auto& x : edge[j])
			{
				int a = x.first, b = x.second;
				if (dis[j] + b < dis[a])
				{
					dis[a] = dis[j] + b;
					judge = true;//有松弛操作
				}
			}
		}
		if (judge == false)break;
	}
	for (int i = 1; i <= n; i++)
	{
		if (dis[i] != INF)cout << dis[i] << " ";
		else cout << INF << " ";
	}
}

int main()
{
	cin >> n >> m >> s;
	for (int i = 1; i <= m; i++)
	{
		int x, y, z; cin >> x >> y >> z;
		edge[x].push_back({ y,z });
	}
	BF();
}

spfa算法：用队列对BF算法进行优化

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N = 1e4 + 10;
const int INF = 2147483647;

typedef pair<int, int> PII;
vector<PII> edge[N];
int dis[N];
int n, m , s;
queue<PII> q;
bool st[N];

void BF()
{
	for (int i = 1; i <= n; i++)dis[i] = INF;
	dis[s] = 0;
	q.push({ s,0 });
	st[s] = true;
	
	while (q.size())
	{
		auto t = q.front(); q.pop();
		int a = t.first, b = t.second;
		for (auto& x : edge[a])
		{
			int y = x.first, z = x.second;
			if (dis[a] + z < dis[y])
			{
				dis[y] = dis[a] + z;
				if(!st[y])
				q.push({ y, dis[y] });
				st[y] = true;
			}
		}

	}

	for (int i = 1; i <= n; i++)
	{
		if (dis[i] != INF)cout << dis[i] << " ";
		else cout << INF << " ";
	}
}

int main()
{
	cin >> n >> m >> s;
	for (int i = 1; i <= m; i++)
	{
		int x, y, z; cin >> x >> y >> z;
		edge[x].push_back({ y,z });
	}
	BF();
}

标准版跑不过：是因为很容易创造数据针对spfa

只是对松弛的进行操作，松弛-进队。

负环P3385 【模板】负环 - 洛谷 

bf算法实现

#include<iostream>
#include<cstring>
using namespace std;

const int N = 2e3 + 10;
const int M = 3e3 + 10;

int T, n, m;
int pos;//记录边的个数
struct node
{
	int u, v, w;
}edge[M*2];
int dis[N];

bool bf()
{
	memset(dis, 0x3f3f3f3f, sizeof(dis));
	dis[1] = 0;//出发点
	bool flag;
	for (int i = 1; i <= n; i++)
	{
		flag = false;
		for (int j = 1; j <= pos; j++)
		{
			int a = edge[j].u, b = edge[j].v, c = edge[j].w;
			if (dis[a] == 0x3f3f3f3f)continue;
			if (dis[a] + c < dis[b])
			{
				dis[b] = dis[a] + c;
				flag = true;
			}
		}
		if (flag == false)return flag;//如果在n-1次到来前退出循环，说明，没有负环，返回false
	}
	return flag;//如果n-1次循环都没有返回false,那么就一定存在负环
}

int main()
{
	cin >> T;
	while (T--)
	{
		cin >> n >> m;
		pos = 0;
		for (int i = 1; i <= m; i++)
		{
			int x, y, z; cin >> x >> y >> z;
			++pos;
			edge[pos].u = x, edge[pos].v = y, edge[pos].w = z;
			if (z >= 0)
			{
				++pos;
				edge[pos].u = y, edge[pos].v = x, edge[pos].w = z;
			}
		}
		if (bf())cout << "YES" << endl;
		else cout << "NO" << endl;
	}
}

spfa算法实现

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>

using namespace std;
typedef pair<int, int> PII;

const int N = 2e3 + 10;
const int M = 3e3 + 10;

int t, n, m;
vector<PII> edge[N];
int dis[N];
bool st[N];
int cnt[N];

bool spfa()
{
	//清除
	memset(dis, 0x3f, sizeof(dis));//一开始无穷大
	memset(cnt, 0, sizeof(cnt));//0
	memset(st, false, sizeof(st));//false
	//初始化
	queue<int> q;
	q.push(1);//推入1
	//初始化
	dis[1] = 0;
	st[1] = true;
	cnt[1] = 0;
	
	while (q.size())
	{
		int x = q.front(); q.pop();
		st[x] = false;
		
		for (auto& ch : edge[x])
		{
			int a = ch.first, b = ch.second;
			if (dis[x] + b < dis[a])
			{
				dis[a] = dis[x] + b;
				if (!st[a])
				{
					q.push(a);
					st[a] = true;
				}
				cnt[a] = cnt[x] + 1;
				if (cnt[a] >= n)return true;
			}
		}
	}
	return false;
}

int main()
{
	cin >> t;
	while (t--)
	{
		//清除
		for (int i = 1; i <= n; i++)edge[i].clear();
		cin >> n >> m;
		//输入
		for (int i = 1; i <= m; i++)
		{
			int a, b, c; cin >> a >> b >> c;
			edge[a].push_back({ b,c });
			if (c >= 0)
			{
				edge[b].push_back({ a,c });
			}
		}
		//大框架
		if (spfa())cout << "YES" << endl;
		else cout << "NO" << endl;
	}
}

总结

例题 

P1629 邮递员送信 - 洛谷（推反图）

#include<iostream>
#include<cstring>
using namespace std;

const int N = 1e3 + 10;
int n, m;
int edge[N][N];
int dis[N];
bool st[N];

void dijkstra()
{
	memset(dis, 0x3f, sizeof(dis));
	memset(st, false, sizeof(st));
	dis[1] = 0;
	for (int i = 1; i <= n; i++)//n次操作
	{
		int t = 0;
		for (int j = 1; j <= n; j++)
		{
			if (!st[j] && dis[j] < dis[t])t = j;//未标记加《dis[t]
		}
		st[t] = true;
		for (int j = 1; j <= n; j++)
		{
			if (!st[j] && edge[t][j]+dis[t] < dis[j])
			{
				dis[j] = edge[t][j] + dis[t];
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	memset(edge, 0x3f, sizeof(edge));
	for (int i = 1; i <= m; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;
		edge[x][y] = min(edge[x][y], z);
	}
	dijkstra();
	int ret = 0;
	for (int i = 1; i <= n; i++)ret += dis[i];
	//推反图
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (i >= j)continue;
			swap(edge[i][j], edge[j][i]);
		}
	}
	dijkstra();
	for (int i = 1; i <= n; i++)ret += dis[i];
	cout << ret << endl;
}

 起点和终点的调换，推反图，他每送完一旦就要返回去，那我们第一次算法，从1到其他店的距离之和记为去的距离，也就可以看成单元最短路问题

而回去的时候，把起点和终点进行调换，变成从其他个点到1的距离，进行调换后，也可以看成单源最短路问题

P1744 采购特价商品 - 洛谷

#include<iostream>
#include<cmath>

using namespace std;

const int N = 110;
const int M = 1010;

int x[N], y[N];//店铺的坐标
struct node
{
	int s;//头
	int e;//尾
	double v;//长
}ed[M];//记录边1

int n;//how many shops
int m;//通路
int star, en;//起点-终点
double dis[N];//起点到各点的距离

double cal(int i, int j)//计算
{
	double a = x[i] - x[j];
	double b = y[i] - y[j];
	return sqrt(a * a + b * b);
}

void BF()
{
	for (int i = 1; i <= n; i++) dis[i] = 1e10;//过大

	dis[star] = 0;
	for (int i = 1; i < n; i++)//n-1次操作
	{
		for (int j = 1; j <= m; j++)//每个边都遍历一遍
		{
			int s = ed[j].s;
			int e = ed[j].e;
			double v = ed[j].v;
			if (dis[s] + v < dis[e])
			{
				dis[e] = dis[s] + v;//更新
			}
			if (dis[e] + v < dis[s])
			{
				dis[s] = dis[e] + v;//更新,重边，没说有向边那就可能存在重边
			}
		}
	}

}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x[i] >> y[i];
	}
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		int a, b; cin >> a >> b;
		ed[i].s = a, ed[i].e = b;
		ed[i].v = cal(a, b);
	}
	cin >> star >> en;
	BF();
	printf("%.2lf", dis[en]);
	return 0;
}

 蠢哭了，两点间距离公式，写成减号半天看不出来

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

P2136 拉近距离 - 洛谷

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
const int M = 1e4+10;

int n, m;

struct node
{
	int x, y, z;
}e[M];
int dis[N];

bool BF(int s)
{
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	bool flag = true;
	for (int i = 1; i <= n; i++)
	{
		flag = false;
		for (int j = 1; j <= m; j++)
		{
			int a = e[j].x, b = e[j].y, c = e[j].z;//老是把这个地方写成i记得改！！！！
			if (dis[a] + c < dis[b])
			{
				dis[b] = dis[a] + c;//更新
				flag = true;//更新
			}
		}
		if (flag == false)return flag;
	}
	return true;
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> e[i].x >> e[i].y >> e[i].z;
		e[i].z = -e[i].z;
	}
	//起点是1
	//双向的求最小
	if (BF(1))
	{
		cout << "Forever love" << endl;//有负环
		return 0;
	}
	int ret1 = dis[n];//记录
	//起点是n
	if (BF(n))
	{
		cout << "Forever love" << endl;//有负环
		return 0;
	}
	int ret2 = dis[1];
	cout << min(ret1, ret2) << endl;
}

 bf或者spfa

双向求最小，两边都要进行遍历

int a = e[j].x, b = e[j].y, c = e[j].z;//老是把这个地方写成i记得改！！！！

P1144 最短路计数 - 洛谷

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;

const int N = 1e6 + 10;
const int M = 2e6 + 10;
const int MOD = 100003;

int n, m;
vector<int> edge[M];
int dis[N];
int f[N];

void bfs()
{
	memset(dis, 0x3f, sizeof(dis));
	//初始化1
	dis[1] = 0;
	f[1] = 1;
	queue<int> q;
	q.push(1);
	while (q.size())
	{
		int t = q.front(); q.pop();
		for (auto& ch : edge[t])
		{
			int b = ch;
			if (dis[t] + 1 < dis[b])//第一次
			{
				dis[b] = dis[t] + 1;
				f[b] = f[t];
				q.push(b);
			}
			else if (dis[t] + 1 == dis[b])
			{
				f[b] = (f[b]+f[t])% MOD;
			}
		}
	}
}
typedef pair<int, int>PII;
bool st[N];
void dijkstra()
{
	memset(dis, 0x3f, sizeof(dis));
	dis[1] = 0;
	f[1] = 1;
	priority_queue<PII,vector<PII>,greater<PII>> q;
	q.push({ 0,1 });
	while (q.size())
	{
		auto t = q.top(); q.pop();
		int a = t.second;

		if (st[a])continue;
		st[a] = true;

		for (auto& ch : edge[a])
		{
			int x = ch;
			
			if (dis[a] + 1 < dis[x])
			{
				f[x] = f[a];
				dis[x] = dis[a] + 1;
				q.push({ dis[x],x });
			}
			else if (dis[a] + 1 == dis[x])
			{
				f[x] = (f[x] + f[a]) % MOD;
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y; scanf("%d%d", &x, &y);
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	/*bfs();*/
	dijkstra();
	for (int i = 1; i <= n; i++)
	{
		printf("%d\n", f[i]);
	}
	return 0;
}

 用bfs和dijkstra算法+动态规划来实现

多源最短路 

B3647 【模板】Floyd - 洛谷

#include<iostream>
#include<cstring>
using namespace std;

const int N = 110;
int f[N][N];
int n, m;

int main()
{
	memset(f, 0x3f, sizeof(f));//对于重边的处理取较小值，所以要把全部都初始化成无穷大，以避免对数据的影响
	cin >> n >> m;
	for (int i = 1; i <= n; i++)//自己到自己都是0
		f[i][i] = 0;
	
	for (int i = 1; i <= m; i++)
	{
		int u, v, w; cin >> u >> v >> w;
		f[u][v] = f[v][u] = min(w, f[u][v]);//对重边+无向图的处理
	}

	for (int k = 1; k <= n; k++)//逐步加入k个点
	{
		for (int i = 1; i <= n; i++)//起点
		{
			for (int j = 1; j <= n; j++)//终点
				f[i][j] = min(f[i][j], f[i][k] + f[k][j]);//k是中转点
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cout << f[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

1. 状态表⽰： f[k][i][j] 表⽰：仅仅经过[1, k] 这些点，结点i ⾛到结点j 的最短路径 的⻓度。

2. 状态转移⽅程：

• 第⼀种情况，不选新来的点： f[k][i][j] = f[k - 1][i][j] ；

• 第⼆种情况，选择新来的点： f[k][i][j] = f[k - 1][i][k] + f[k - 1][k][j]，

i->k的路径+k到j的路径之和，把k作为中转点。找以k为中转点，i到j是否存在更小的路径，存在的话，那就更新，不在的话，那就维持原判。

3. 空间优化：只会⽤到上⼀层的状态，因此可以优化到第⼀维。

4. 初始化：

• f[i][i] = 0 ；

• f[i][j] 为初始状态下i 到j 的距离，如果没有边则为⽆穷。

5. 填表顺序：

• ⼀定要先枚举k ，再枚举i 和j 。因为我们填表的时候，需要依赖的是k - 1 层的状态，因 此k 必须先枚举。

P2910 [USACO08OPEN] Clear And Present Danger S - 洛谷

#include<iostream>

using namespace std;
const int N = 110;
const int M = 1e4 + 10;
int n, m;
int a[M];
int f[N][N];
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)cin >> a[i];

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> f[i][j];

	//floyd算法
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
				f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
		}
	}
	//加上
	long long ret = 0;
	for (int i = 1; i < m; i++)
	{
		ret += f[a[i]][a[i+1]];
	}
	cout << ret << endl;
}

 P1119 灾后重建 - 洛谷

 本题的t是保证不下降的->可以使用floyd算法不断加点。

#include<iostream>
#include<cstring>
using namespace std;
const int N = 210;
const int M = 2e4 + 10;
const int INF = 0x3f3f3f3f;

int f[N][N];
int t[N];
int n, m;

void floyd(int k)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
		}
	}
}

int main()
{
	cin >> n >> m;
	memset(f, INF, sizeof(f));
	for (int i = 0; i < n; i++)f[i][i] = 0;

	for (int i = 0; i < n; i++)cin >> t[i];

	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		f[a][b] = f[b][a] = min(f[a][b], c);//无向边的处理,!!!!!!
	}
	int q; cin >> q;
	int pos = 0;
	while (q--)
	{
		int a, b, c; cin >> a >> b >> c;
		while (pos<n&&t[pos] <= c)//pos记录当前符合时间条件可以加进去的地点,不可以超过n
			floyd(pos++);
		}
		if (t[a] > c || t[b] > c || f[a][b] == INF)cout << -1 << endl;
		else cout << f[a][b] << endl;
	}
	return 0;
}

 P6175 无向图的最小环问题 - 洛谷

 从上面找最小环

下面用floyd算法找最小距离

#include<iostream>

using namespace std;
const int N = 110;
const int M = 5e3 + 10;
const int INF = 1e8;
int n, m;

int e[N][N];
int f[N][N];

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			e[i][j] = e[j][i] = f[i][j] = f[j][i] = INF;
		}
	}
	for (int i = 1; i <= m; i++)
	{
			int a, b, c; cin >> a >> b >> c;
			e[a][b] = e[b][a] = f[a][b] = f[b][a] = min(f[a][b], c);
	}
	int ret = INF;
	for (int k = 1; k <= n; k++)
	{
        //最小环
		for (int i = 1; i < k; i++)
		{
			for (int j = i + 1; j < k; j++)
			{
				ret = min(ret, f[i][j] + e[i][k] + e[k][j]);
			}
		}
        //最小距离
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
				f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
		}
	}
	if (ret == INF)cout << "No solution." << endl;
	else cout << ret << endl;
	return 0;
}