最短路问题+最小生成树

最短路问题+最小生成树

1.Floyd算法

 能解决大多数的图 但是复杂度大，时间复杂度O（N^3)

对于Floyd而已一次预处理后可以知道任意两点的最短距离，值得注意的是要先将dist初始化，i==j情况下为0，即自己和自己的距离，千万不要inf，然后就是三次for遍历跑一次

 初始化：

	int k;cin >> n >> m >> k;for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)dist[i][j] = i == j ? 0 : inf;

核心算法： 

void Floyd() {for (int k = 1; k <= n; ++ k){for (int j = 1; j <= n; ++j){for (int g = 1; g <= n; ++g){dist[j][g] = min(dist[j][g], dist[j][k] + dist[k][g]);}}}
}

 2.Bellman_Floyd算法

    可以解决负环问题

Bellman-floyd算法基础模板题牛客

 代码实现

#include<iostream>
#include<algorithm>
#include<string.h>
#include <set>
#include<cstdio>
#include <vector>
#include<map>
#include<string>
#include<cstring>
#include<numeric> 
#include<math.h>
#include<queue>
#include <functional>
#include <bits/stdc++.h>
#include<unordered_map>
using  namespace std;#define Fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define SQR(i) fixed<<setprecision(i)
#define int long long
typedef long long ll;
#define endl 'n'
#define int long long
#define inf 0x3f3f3f3f
#define inf_max 0x7f7f7f7fint n, m, s, t;
int dis[20000];struct node
{int v, w;
};
vector<node>arr[20000];void Bellman_Ford(int s) {for (int i = 1; i <= n; ++i) {dis[i] = inf;}dis[s] = 0;for(int k=1;k<n;++k)//迭代n-1次，每次更新一个for (int i = 1; i <= n; ++i)//对于第一个i找他匹配的所有边for (int j = 0; j < arr[i].size(); ++j)//对于每条边进行判断{int u = i, v = arr[i][j].v, w = arr[i][j].w;if (dis[v] > dis[u] + w)dis[v] = dis[u] + w;}//if i==n 则出现了重环必错
}void Solve() {cin >> n >> m >> s >> t;for (int i = 0; i < m; ++i){int u, v, w;cin >> u >> v >> w;arr[u].push_back({ v,w });arr[v].push_back({ u,w });}Bellman_Ford(s);if (dis[t] > inf / 2)cout << -1 << endl;else cout << dis[t] << endl;}signed main()
{std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int t;Solve();
}

当然也可以这个样子存图，效果一样：

int n, m, s, t;
int dis[20000];struct node
{int u, v, w;
};
vector<node>arr;void Bellman_Ford(int s) {for (int i = 1; i <= n; ++i) {dis[i] = inf;}dis[s] = 0;for (int i = 1; i < n; ++i){for (int j = 0; j < 2 * m; ++j){int u = arr[j].u, v = arr[j].v, w = arr[j].w;if (dis[v] >dis[u] + w )dis[v] = dis[u] + w;}}}void Solve() {cin >> n >> m >> s >> t;for (int i = 0; i < m; ++i){int u, v, w;cin >> u >> v >> w;arr.push_back({ u,v,w });arr.push_back({ v,u,w });}Bellman_Ford(s);if (dis[t] > inf / 2)cout << -1 << endl;else cout << dis[t] << endl;}

对于Bellman_Floyd 算法的队列优化 SPFA优化;

//关于为什么要更新n-1次的问题！！！！

for k:n-1    这里的k是不超过k条边 如果k==n，一定存在负环！！！！！！

 

 SPFA优化代码: 它也可以判断是否存在负环！！！！

int n, m, s, t;
int dis[20000];
bool vis[20000];
struct node
{int v, w;
};
vector<node>arr[20000];
int cnt[20000];void SPFA(int s) {for (int i = 0; i <= n; ++i)dis[i] = inf;dis[s] = 0; vis[s] = true;queue<int>q;q.push(s);while (!q.empty()){int t = q.front();q.pop();vis[t] = false;//使得队首可以入队for (int i = 0; i < arr[t].size(); ++i) {int j = arr[t][i].v;int w = arr[t][i].w;if (dis[j] > dis[t] + w) {dis[j] = dis[t] + w;cnt[j] = cnt[t] + 1;//判断负环//if (cnt[j] >= n) 等于n说明了负环！！！//{//	cout << "找到了负环" << endl;//}if (!vis[j])q.push(j), vis[j] = true;}}}
}

Attention:

        是不是存在负环是要把所有点压入queue，因为题目不是求从1点开始的负环，是所有点的负环！！！ 如果改成从1开始的负环就不需要！！！

    for (int i = 1; i <= n; ++i)q.push(i);

3.1.Dijkstra求最短路 I：

 

朴素的Dijkstra()算法：

void Dij(int s)
{for (int i = 0; i <= n; ++i)dis[i] = inf, vis[i] = false;dis[s] = 0;for (int i = 1; i <= n; ++i) {//循环n次int t = -1;for (int j = 1; j <=n; ++j) {//找未标记中最小的dis的节点xif (!vis[i] && (t == -1 || dis[j] < dis[t]))t = j;if (t == -1)return;vis[t] = true;for (int j = 1; j <=n; ++j)//从想出发更新dis[j] = min(dis[j], dis[t] + arr[t][j]);}}
}

 优先队列堆优化的Dijkstra算法：

void Dijkstra(int s) {for (int i = 0; i <= n; ++i)dis[i] = inf, vis[i] = false;dis[s] = 0;priority_queue<PII, vector<PII>, greater<PII> >q;q.push({ 0,s });//0是dis， s是当然点while(!q.empty()){int t = q.top().second;//取出队首q.pop();if (vis[t])continue;//访问了就continuevis[t] = true;for (int i = 0, len = arr[t].size(); i < len; ++i) {//对于t这个点遍历更新和它匹配的点int v = arr[t][i].v, w = arr[t][i].w;if (dis[v] > dis[t] + w)//符合就更新后压入dis[v] = dis[t] + w, q.push({ dis[v],v });}}
} 

void Dijkstra(int s) {for(int i=0; i<=2*n; ++i)dis[i]=inf,vis[i]= false;dis[s]=0;priority_queue<PII,vector<PII>,greater<PII> >q;//first is dis  y is startwhile (!q.empty()) {				//清空队列q.pop();}q.push({0,s});while(!q.empty()) {int t&#p().second;q.pop();if(vis[t])continue;vis[t]=true;for(int i=0,len=arr[t].size(); i<len; ++i) {int v=arr[t][i].v,w=arr[t][i].w;if(!vis[v]&&dis[v]>dis[t]+w)dis[v]=dis[t]+w,q.push({dis[v],v});}}
}

 

!!!!!题源this->

 这是狄斯克算法，权值有向图；数据域小直接开数组：当然这是没有优化的算法，复杂度为O(n^2)，我们可以采取优先队列进行最短路堆优化

#include<bits/stdc++.h>
using namespace std;
#define endl 'n'
#define inf 0x3f3f3f3f
typedef long long ll;
int a[505][505],dis[5000];//dis为到达节点的路，a为图
bool vis[5000];//标记集合
void Solve() {int n,m;cin>>n>>m;memset(a,inf,sizeof a);//inf 数组afor(int i=1;i<=m;++i){int x,y,w;cin>>x>>y>>w;a[x][y]=min(a[x][y],w);}// 存图for(int i=1;i<=n;++i)a[i][i]=0;memset(dis,inf,sizeof dis);//dis INFdis[1]=0;for(int cnt=1;cnt<=n;++cnt)//扩扑n次{int min_val=inf,x;for(int i=1;i<=n;++i)//更新最短路if(!vis[i]&&dis[i]< min_val)min_val=dis[i],x=i;vis[x]=true;//标记已经用过for(int y=1;y<=n;++y)//更新dis[y]=min(dis[y],dis[x]+a[x][y]);}if(dis[n]==inf)cout<<-1<<endl;else cout<<dis[n]<<endl;
}
signed main() {std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);Solve();}

 3.2.Dijkstra求最短路 II（最短路堆优化）：

题源在这里哦

---

显然本题 数据域范围过大存图要么连接表要么开维克多数组，这里我们使用优先队列，这个样子可以对最短路堆优化

---

连接表：

//连接表
const int MAX_N=2e5+5,MAX_M=2e5+5;
int head[MAX_N],ver[MAX_M],edge[MAX_M],nxt[MAX_M],tot;
//插入一条x到y长度z的有向边
void add(int x,int y,int z)
{tot++;ver[tot]=y;edge[tot]=z;nxt[tot]=head[x];//在head[x]这条链开头插入新点head[x]=tot;
}

 AC代码：注意的是优先队列是大顶堆，降序，可以加-使其升序或者重载struct

#include<bits/stdc++.h>
using namespace std;
#define endl 'n'
#define inf 0x3f3f3f3f
#define inf_max 0x7f7f7f7f
typedef long long ll;const int MAX_N=2e5+5,MAX_M=2e5+5;
int head[MAX_N],ver[MAX_M],edge[MAX_M],nxt[MAX_M],tot;
//插入一条x到y长度z的有向边
void add(int x,int y,int z)
{tot++;ver[tot]=y;edge[tot]=z;nxt[tot]=head[x];//在head[x]这条链开头插入新点head[x]=tot;
}
int n,m,dis[MAX_M];
bool vis[MAX_M];
//pair(dist[x],x)
struct com{bool operator()(pair<int,int>a,pair<int,int>b){return a.first<b.first;}
};
priority_queue<pair<int,int> > q;//大顶堆;
void Solve() {cin>>n>>m;for(int i=1;i<=m;++i){int x,y,z;cin>>x>>y>>z;add(x,y,z);}//存图memset(dis,inf_max,sizeof dis);dis[1]=0;q.push(make_pair(0,1));while(!q.empty()){int x&#p().second;q.pop();if(vis[x])continue;vis[x]=true;for(int i=head[x];i;i=nxt[i]){int y=ver[i],z=edge[i];if(dis[y]>dis[x]+z){dis[y]=dis[x]+z;q.push(make_pair(-dis[y],y));}}}if(dis[n]==inf_max)cout<<-1<<endl;else cout<<dis[n]<<endl;
}
signed main() {std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);Solve();}

4.路径打印和路径统计问题

 路径统计问题-洛谷

最短路典型问题：

1. 有边数限制的最短路

有边数限制的最短路--ACwing

题解：

值得一提的是这题只可以Bellman算法，因为外层k循环是使得不超过k层边！！！

 //防止串联，添加备份！！！！！      

        back干啥使的
back[j]表示每次进入第2重循环的dist数组的备份。
如果不加这个备份的话有可能会发生节点最短距离的串连；
比如说：
图1
现在从3号结点走到4号节点要想进行松弛操作就必须先得到dist[3]，要想得到dist[3]就得知道dist[2]；
dist[2]=2，现在dist[3]是正无穷，用2号结点来更新3号结点，dist[3]=2+3=5;

现在要更新dist[4]了，此时dist[4]=正无穷

出现问题了，dist[4]是用dist[3]是用正无穷来更新还是5呢

用dist[3]=5来更新那是下一次i迭代的事情；
这道题说是不经过k条边，说不定下一次就到k条边了，所以还是得用正无穷来更新的

#include <bits/stdc++.h>
#include<unordered_map>
using  namespace std;
#define Fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef pair<int, int > PII;
#define SQR(i) fixed<<setprecision(i)
#define int long long
typedef long long ll;
#define endl 'n'
const int N = 2e5 + 5;
#define int long long
#define iaa ((1ll<<31)<<31)-1
#define inf  12345678090int n,m,s;
bool vis[10500];
struct node{int v,w;
};
vector<node>arr[10500];
int dis[10500];int back[N];//备份数组放置串联
void Bellman_Ford(int s) {memset(dis,inf,sizeof dis);dis[1] = 0;for(int k=0;k<s;++k)//迭代n-1次，每次更新一个{memcpy(back, dis, sizeof dis);for (int i = 1; i <= n; ++i) {//对于第一个i找他匹配的所有边for (int j = 0; j < arr[i].size(); ++j)//对于每条边进行判断{int u = i, v = arr[i][j].v, w = arr[i][j].w;//if (dis[v] > dis[u] + w)dis[v] = dis[u] + w;dis[v]=min(dis[v],back[u]+w);}}}
}void Solve() {cin>>n>>m>>s;for(int i=0; i<m; ++i) {int u,v,w;cin>>u>>v>>w;arr[u].push_back({v,w});// arr[v].push_back({u,w});}Bellman_Ford(s);if(dis[n]>inf/2)cout<<"impossible"<<endl;else cout<<dis[n]<<endl;
}
signed main()
{Fast;Solve();return 0;
}

当然本题也可以不需要邻接表！！

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int dist[N],backup[N];
int k,n,m;
struct edge{int a;int b;int w;
}edge[N];
int bellman_ford()
{memset(dist,0x3f,sizeof dist);dist[1]=0;for(int i=1;i<=k;i++){memcpy(backup,dist,sizeof dist);for(int j=1;j<=m;j++){int a=edge[j].a,b=edge[j].b,w=edge[j].w;dist[b]=min(dist[b],backup[a]+w);}}if(dist[n]>=0x3f3f3f3f/2)return -1;else return dist[n];
}
int main()
{cin>>n>>m>>k;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;edge[i].a=a,edge[i].b=b,edge[i].w=c;}int t=bellman_ford();if(t==-1)puts("impossible");else cout<<t<<endl;
}

5.最小生成树

1、什么是树

如果一个无向连通图不包含回路(连通图中不存在环),那么就是一个树。

参考文章！最小生成树

2..prim（）算法

int prime()
{//1memset(d,0x3f,sizeof d);d[1] = 0;//2int res = 0;//权重之和for(int i = 0;i<n;i++)//循环n次{//(1)不属于集合 && 距离集合最小的点int t = -1;for(int j = 1;j<=n;j++){if(!st[j] && (t == -1 || d[t] > d[j]))//t = j;}if(d[t] == INF) return INF;//(3)-把点t加到集合当中去，更新权值res += d[t];st[t] = true;//(2)for(int j = 1;j<=n;j++) d[j] = min(d[j],g[t][j]);}return res;
}

3.Kruskal算法

先将边权重按照从小到大排序，然后依次遍历对于不在同一集合的进行合并，ans是答案，使用了并查集知识，cnt<n-1表示无法得到最小生成树

Kruskal算法题目

int n, m;
int ans;//最小权重和
int p[N];
struct edge {int a, b, w;//重载<bool operator<(const edge& W)const{return w < W.w;//从小到大}
}edge[N];int find(int x)
{return p[x] == x ? x : p[x] = find(p[x]);
}
int Kruskal()
{int cnt = 0;sort(edge, edge + m);for (int i = 0; i <= n; ++i)p[i] = i;//初始化并查集for (int i = 0; i < m; ++i)//遍历{int a = edge[i].a, b = edge[i].b, w = edge[i].w;a = find(a); b = find(b);if (a != b)///a b不相等就合并{p[a] = b;ans += w;cnt++;}}return cnt;//cnt<n-1 说明了没用最小生成树}void Solve() {cin >> n >> m;for (int i = 0; i < m; ++i){int u, v, w;cin >> edge[i].a >> edge[i].b >> edge[i].w;}int t = Kruskal();if (t < n - 1)cout << "impossible" << endl;else cout << ans << endl;
}