spfa和寻找负权环模板()-其他
spfa和寻找负权环模板()
负权环：模板题目链接：https://www.luogu.com.cn/problem/P3385
1 #include<iostream>
2 #include<cstdio>
3 #include<cstdlib>
4 #include<algorithm>
5 #include<cmath>
6 #include<string>
7 #include<stack>
8 #include<queue>
9 #include<cstring>
10 #include<map>
11 #include<iterator>
12 #include<list>
13 #include<set>
14 #include<functional>
15 #include<memory.h>//手滑复制的那么多
16
17 using namespace std;
18
19 const int maxn=5005;//顶点最大数
20 const int M=5005;//边最大数
21 const int inf=0x3f3f3f3f;
22 int n,m;//顶点数与边数。
23 int tot;//递增序号，用来存储。
24 int cnt[maxn];//cnt[i]记录的是i顶点的入队次数。若大于n，则必然存在负环。
25 typedef struct Edge{
26 int next;//当前边的下一条边。
27 int to;//边的终端节点
28 int w;//边权值。
29 }Edge;
30 Edge edge[M];//用边来表示图。
31 int head[maxn];//head[i]表示以i为起点的第一条边的编号，若为-1则表示以该起点没有边。
32 int dis[maxn];//存储所有顶点到源点的距离。
33 bool visited[maxn];//判断是否在队列中。
34 void init(){//初始化
35 memset(dis,inf,sizeof(dis));//距离初始化
36 memset(visited,false,sizeof(visited));//初始没有访问过
37 memset(head,-1,sizeof(head));//head就是最后一个起点为i的边的下表，在链式前向星里就是next
38 memset(cnt,0,sizeof(cnt));//计数器
39 tot=0;
40 }
41 void add(int u,int v,int w){//建图
42 edge[tot].to=v;
43 edge[tot].w=w;
44 edge[tot].next=head[u];//插在第一条边前面。
45 head[u]=tot++;//改变第一条边的编号。
46 //因为要从0开始，所以不用++tot，初始化为0
47 }
48 int spfa(int S){//S为起点，其实直接写1也没事
49 queue<int> q;
50 dis[S]=0;
51 int temp;
52 q.push(S);
53 cnt[S]++;//起点计数器+1
54 visited[S]=true;
55 int flag=0;//标志位，判断是否存在负环。
56 while(!q.empty()){
57 temp=q.front();
58 q.pop();
59 visited[temp]=false;
60 int v,w;
61 for(int i=head[temp];i!=-1;i=edge[i].next){//倒着遍历，因为初始head为-1
62 v=edge[i].to;//保存边的终端节点。
63 w=edge[i].w;//保存边权值。
64 if(dis[v]>dis[temp]+w){
65 //松弛操作。
66 dis[v]=dis[temp]+w;
67 if(!visited[v]){
68 q.push(v);
69 cnt[v]++;//每次松弛入队就++
70 if(cnt[v]>n){flag=1;return flag;}//有负环
71 visited[v]=true;
72 }
73 }
74 }
75 }
76 return flag;
77 }
78 int main(){
79 int t;
80 cin >> t;
81 while(t--){//t个数据
82 cin >> n >> m;//n个点，m条边
83 int u,v,w;
84 init();//初始化
85 for(int i=0;i<m;i++){
86 cin>>u>>v>>w;
87 add(u,v,w);
88 if(w>=0)
89 add(v,u,w);
90 }
91 int S=1;//起点与终点。
92 int result=spfa(S);
93 if(result)cout<<"YES"<<endl;
94 else cout<<"NO"<<endl;
95 }
96 return 0;
97 }vector链接表做法
1 #include<bits/stdc++.h>
2 #define inf 2147483647
3
4 using namespace std;
5
6 int n , m , s;
7 int vis[10005],d[10005];
8 struct edge{
9 int v;
10 int w;
11 };
12 vector<edge>adj[10005]; //开一个vector动态数组 ，注意这是有向图
13
14 void spfa()
15 {
16 for(int i = 1 ; i <= n; i ++)
17 d[i] = inf;//距离都赋值为最大值，以后松弛替换
18 queue<int>q;
19 q.push(s);
20 vis[s] = 1;
21 d[s] = 0;
22 while(!q.empty())
23 {
24 int u = q.front();
25 q.pop();
26 vis[u] = 0;
27 for(int i = 0 ; i < adj[u].size(); i ++)//vector可以理解为1个竖着的数组
28 //如果一个点存在多个出度，可以在从这横向延申，size（）便是的长度
29 {//遍历每条边
30 int v = adj[u][i].v;
31 int w = adj[u][i].w;
32 if(d[u]+w<d[v])//松弛
33 {
34 d[v] = d[u]+w;
35 if(vis[v]==0)
36 {
37 vis[v]=1;
38 q.push(v);
39 }
40 }
41 }
42 }
43 }
44
45 int main()
46 {
47 scanf("%d%d%d",&n,&m,&s);//n个点，m条边，出发点为s
48 for(int i = 1 ; i <= m ; i ++)
49 {
50 int u,v,w;
51 scanf("%d%d%d",&u,&v,&w);
52 edge a;
53 a.v = v;
54 a.w = w;
55 adj[u].push_back(a);//存边，只用1个，无向图再加一个
56 }
57 spfa();
58 for(int i = 1 ; i <= n ; i ++)
59 {
60 cout<<d[i]<<" ";//输入从s到每个点的最短路
61 }
62 } ————————
负权环：模板题目链接：https://www.luogu.com.cn/problem/P3385
1 #include<iostream>
2 #include<cstdio>
3 #include<cstdlib>
4 #include<algorithm>
5 #include<cmath>
6 #include<string>
7 #include<stack>
8 #include<queue>
9 #include<cstring>
10 #include<map>
11 #include<iterator>
12 #include<list>
13 #include<set>
14 #include<functional>
15 #include<memory.h>//手滑复制的那么多
16
17 using namespace std;
18
19 const int maxn=5005;//顶点最大数
20 const int M=5005;//边最大数
21 const int inf=0x3f3f3f3f;
22 int n,m;//顶点数与边数。
23 int tot;//递增序号，用来存储。
24 int cnt[maxn];//cnt[i]记录的是i顶点的入队次数。若大于n，则必然存在负环。
25 typedef struct Edge{
26 int next;//当前边的下一条边。
27 int to;//边的终端节点
28 int w;//边权值。
29 }Edge;
30 Edge edge[M];//用边来表示图。
31 int head[maxn];//head[i]表示以i为起点的第一条边的编号，若为-1则表示以该起点没有边。
32 int dis[maxn];//存储所有顶点到源点的距离。
33 bool visited[maxn];//判断是否在队列中。
34 void init(){//初始化
35 memset(dis,inf,sizeof(dis));//距离初始化
36 memset(visited,false,sizeof(visited));//初始没有访问过
37 memset(head,-1,sizeof(head));//head就是最后一个起点为i的边的下表，在链式前向星里就是next
38 memset(cnt,0,sizeof(cnt));//计数器
39 tot=0;
40 }
41 void add(int u,int v,int w){//建图
42 edge[tot].to=v;
43 edge[tot].w=w;
44 edge[tot].next=head[u];//插在第一条边前面。
45 head[u]=tot++;//改变第一条边的编号。
46 //因为要从0开始，所以不用++tot，初始化为0
47 }
48 int spfa(int S){//S为起点，其实直接写1也没事
49 queue<int> q;
50 dis[S]=0;
51 int temp;
52 q.push(S);
53 cnt[S]++;//起点计数器+1
54 visited[S]=true;
55 int flag=0;//标志位，判断是否存在负环。
56 while(!q.empty()){
57 temp=q.front();
58 q.pop();
59 visited[temp]=false;
60 int v,w;
61 for(int i=head[temp];i!=-1;i=edge[i].next){//倒着遍历，因为初始head为-1
62 v=edge[i].to;//保存边的终端节点。
63 w=edge[i].w;//保存边权值。
64 if(dis[v]>dis[temp]+w){
65 //松弛操作。
66 dis[v]=dis[temp]+w;
67 if(!visited[v]){
68 q.push(v);
69 cnt[v]++;//每次松弛入队就++
70 if(cnt[v]>n){flag=1;return flag;}//有负环
71 visited[v]=true;
72 }
73 }
74 }
75 }
76 return flag;
77 }
78 int main(){
79 int t;
80 cin >> t;
81 while(t--){//t个数据
82 cin >> n >> m;//n个点，m条边
83 int u,v,w;
84 init();//初始化
85 for(int i=0;i<m;i++){
86 cin>>u>>v>>w;
87 add(u,v,w);
88 if(w>=0)
89 add(v,u,w);
90 }
91 int S=1;//起点与终点。
92 int result=spfa(S);
93 if(result)cout<<"YES"<<endl;
94 else cout<<"NO"<<endl;
95 }
96 return 0;
97 }vector链接表做法
1 #include<bits/stdc++.h>
2 #define inf 2147483647
3
4 using namespace std;
5
6 int n , m , s;
7 int vis[10005],d[10005];
8 struct edge{
9 int v;
10 int w;
11 };
12 vector<edge>adj[10005]; //开一个vector动态数组 ，注意这是有向图
13
14 void spfa()
15 {
16 for(int i = 1 ; i <= n; i ++)
17 d[i] = inf;//距离都赋值为最大值，以后松弛替换
18 queue<int>q;
19 q.push(s);
20 vis[s] = 1;
21 d[s] = 0;
22 while(!q.empty())
23 {
24 int u = q.front();
25 q.pop();
26 vis[u] = 0;
27 for(int i = 0 ; i < adj[u].size(); i ++)//vector可以理解为1个竖着的数组
28 //如果一个点存在多个出度，可以在从这横向延申，size（）便是的长度
29 {//遍历每条边
30 int v = adj[u][i].v;
31 int w = adj[u][i].w;
32 if(d[u]+w<d[v])//松弛
33 {
34 d[v] = d[u]+w;
35 if(vis[v]==0)
36 {
37 vis[v]=1;
38 q.push(v);
39 }
40 }
41 }
42 }
43 }
44
45 int main()
46 {
47 scanf("%d%d%d",&n,&m,&s);//n个点，m条边，出发点为s
48 for(int i = 1 ; i <= m ; i ++)
49 {
50 int u,v,w;
51 scanf("%d%d%d",&u,&v,&w);
52 edge a;
53 a.v = v;
54 a.w = w;
55 adj[u].push_back(a);//存边，只用1个，无向图再加一个
56 }
57 spfa();
58 for(int i = 1 ; i <= n ; i ++)
59 {
60 cout<<d[i]<<" ";//输入从s到每个点的最短路
61 }
62 }