526互联

CSP_J 暑假清北学堂集训 第四天

发布时间 2023-07-12 17:01:58作者: Slz_konnyaku

一、最短路基础理论

disi,jdisi,j​ 代表 i->j 的最短路

性质：disi,j<disi,k+disk,jdisi,j​<disi,k​+disk,j​ -> 三角不等式

1.单源最短路

定义：一个起点到其他点的最短路

2.多源最短路

定义：多个起点到其他点的最短路

二、最短路算法 -> floyd

disti,j,kdisti,j,k​ 含义

从 jj 到 kk 的最短路，但中间节点编号要 ≤i≤i

求 jj 到 kk 的最短路就是 distn,j,kdistn,j,k​

dist0,j,kdist0,j,k​ 的值分两种情况

1.jj 和 kk 之间有边，dist0,j,k=ddist0,j,k​=d

2.无边，dist0,j,k=0x3fdist0,j,k​=0x3f（无穷大）

在 i≠0i​=0 的情况下，再分两种情况

1.节点编号 <i<i 等同于 ≤i−1≤i−1，所以答案是 disti−1,j,kdisti−1,j,k​

2.节点编号 ≤i≤i 代表节点中经过 ii 相当于前半部分到点 ii 最短路加从 ii 到后半部分最短路

代码

#include<bits/stdc++.h>
#define ll long long
#define itn int

using namespace std;

const int maxn=15;
int dist[maxn][maxn][maxn]; 
//dist[i][j][k]代表 从j走到k 使得中间经过节点编号 <=i 的情况下最短 
const int INF=0x3f3f3f3f;
int n,m;

int main(){
    memset(dist,0x3f,sizeof dist);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int s,e,d;
        cin>>s>>e>>d;
        //一条从s到e 长度为d的边 
        dist[0][s][e]=min(dist[0][s][e],d);
    }
    for(int i=1;i<=n;i++){
        dist[0][i][i]=0;
        //任何点到自身的最短路是0 
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                dist[i][j][k]=min(dist[i-1][j][k],dist[i-1][j][i]+dist[i-1][i][k]);
            }
        }
    } 
    //O(n^3) 
    return 0;
}

压维

#include<bits/stdc++.h>
#define ll long long
#define itn int

using namespace std;

const int maxn=15;
int dist[maxn][maxn]; 
//dist[i][j][k]代表 从j走到k 使得中间经过节点编号 <=i 的情况下最短 
const int INF=0x3f3f3f3f;
int n,m;

int main(){
    memset(dist,0x3f,sizeof dist);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int s,e,d;
        cin>>s>>e>>d;
        //一条从s到e 长度为d的边 
        dist[s][e]=min(dist[s][e],d);
    }
    for(int i=1;i<=n;i++){
        dist[i][i]=0;
        //任何点到自身的最短路是0 
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k]);
            }
        }
    } 
    //O(n^3) 
    return 0;
}

三、单源最短路算法

1.dijkstra

条件：边长度 ≤0≤0

思路详见代码：

//每一轮选一个已经求好的点
//进行松弛操作 
//用自己的最短路更新周围点的最短路
#include<bits/stdc++.h>
#define ll long long
#define itn int

using namespace std;

const int maxn=1005;
int dist[maxn];
//从s到i的最短路 
bool vis[maxn];
//每个点有没有求出最短路 
int n,m;
int s,e,d;
vector<pair<int,int> > a[maxn];

void add_edge(int s,int e,int d){
    a[s].push_back(make_pair(e,d));
}
void dijkstra(int s){
    //O(n^2+m)
    memset(dist,0x3f,sizeof(dist));
    dist[s]=0;
    for(int i=1;i<=n;i++){
        //选一个dist最小的点
        int p=0;
        for(int j=1;j<=n;j++){
            //O(n^2)
            if(!vis[j]&&(p==0||dist[j]<dist[p])) p=j;
        } 
        vis[p]=true;//这个点已经选过 
        //用这个点松弛操作
        for(int j=0;j<a[p].size();j++){
            int q=a[p][j].first;
            int d=a[p][j].second;
            //这是一条从p到q长度为d的边
            if(dist[q]>dist[p]+d) dist[q]=dist[p]+d; 
            //O(m)
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>s>>e>>d;
        add_edge(s,e,d);
    }
    dijkstra(1);
    return 0;
}

2.堆优化

//每一轮选一个已经求好的点
//进行松弛操作
//用自己的最短路更新周围点的最短路
#include<bits/stdc++.h>
#define ll long long
#define itn int

using namespace std;

const int maxn=1005;
int dist[maxn];
//从s到i的最短路
bool vis[maxn];
//每个点有没有求出最短路
int n,m;
int s,e,d;
vector<pair<int,int> > a[maxn];

void add_edge(int s,int e,int d) {
    a[s].push_back(make_pair(e,d));
}
void dijkstra(int s) {
    //O((n+m)log(n+m))
    memset(dist,0x3f,sizeof(dist));
    dist[s]=0;
    priority_queue<pair<int,int> > heap;
    //first用来存距离的相反数
    //second用来存点的编号
    //pair比较时优先比较first

    for(int i=1;i<=n;i++)
        heap.push(make_pair(-dist[i],i));
    for(int i=1; i<=n; i++) {
        //选一个dist最小的点
        while(vis[heap.top().second]){
            heap.pop();
        }
        int p=heap.top().second;
        heap.pop();
        vis[p]=true;//这个点已经选过
        //用这个点松弛操作
        for(int j=0; j<a[p].size(); j++) {
            int q=a[p][j].first;
            int d=a[p][j].second;
            //这是一条从p到q长度为d的边
            if(dist[q]>dist[p]+d){
                dist[q]=dist[p]+d;
                heap.push(make_pair(-dist[q],q));
                //更新最短路 
            }
        }
    }
}

int main() {
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        cin>>s>>e>>d;
        add_edge(s,e,d);
    }
    return 0;
}

3.bellman-ford算法

代码：

#include<bits/stdc++.h>
#define ll long long
#define itn int

using namespace std;

const int maxn=1005;
int n,m;
int s[maxn],e[maxn],d[maxn];
int dist[maxn];

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>s[i]>>e[i]>>d[i];
    }
    memset(dist,0x3f,sizeof (dist));
    dist[1]=0;

    for(int i=1;i<n;i++){
        for(int j=1;j<=m;j++){
            dist[e[j]]=min(dist[e[j]],dist[s[j]]+d[j]);
        }
    }
    //O(mn)
    return 0;
}

4.spfa

#include<bits/stdc++.h>
#define ll long long
#define itn int

using namespace std;

const int maxn=1005;
int dist[maxn];
//从s到i的最短路 
bool vis[maxn];
//每个点有没有求出最短路 
int n,m;
int s,e,d;
vector<pair<int,int> > a[maxn];

void add_edge(int s,int e,int d){
    a[s].push_back(make_pair(e,d));
}
void spfa(int s){
    memset(dist,0x3f,sizeof(dist));
    dist[s]=0;
    queue<int> q;
    q.push(s);
    vis[s]=true;
    //最坏O(nm)
    //一般O(km) k 100~200 
    while(q.size()){
        int p=q.front();
        q.pop();
        vis[p]=false;
        for(int i=0;i<a[p].size();i++){
            int e=a[p][i].first;
            int d=a[p][i].second;
            if(dist[e]>dist[p]+d){
                dist[e]=dist[p]+d;
                if(!vis[e]){
                    q.push(e);
                    vis[e]=true;
                }
            }
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>s>>e>>d;
        add_edge(s,e,d);
    }
    spfa(1);
    return 0;
}

四、最短路算法

1.多源最短路：Floyd

2.单源最短路：

边权>=0 -> dijkstra堆优化版

边权<0 -> spfa

五、判断负环方法：

1.卡时

#include<bits/stdc++.h>
#define ll long long
#define itn int

using namespace std;

const int maxn=1005;
int dist[maxn];
//从s到i的最短路 
bool vis[maxn];
//每个点有没有求出最短路 
int n,m;
int s,e,d;
vector<pair<int,int> > a[maxn];

void add_edge(int s,int e,int d){
    a[s].push_back(make_pair(e,d));
}
void spfa(int s){
    if(clock*1000>=900*CLOCKS_PER_SEC){
        puts("有负环");
        exit(0);
    } 
    memset(dist,0x3f,sizeof(dist));
    dist[s]=0;
    queue<int> q;
    q.push(s);
    vis[s]=true;
    //最坏O(nm)
    //一般O(km) k 100~200 
    while(q.size()){
        int p=q.front();
        q.pop();
        vis[p]=false;
        for(int i=0;i<a[p].size();i++){
            int e=a[p][i].first;
            int d=a[p][i].second;
            if(dist[e]>dist[p]+d){
                dist[e]=dist[p]+d;
                if(!vis[e]){
                    q.push(e);
                    vis[e]=true;
                }
            }
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>s>>e>>d;
        add_edge(s,e,d);
    }
    spfa(1);
    return 0;
}

2.科学法

#include<bits/stdc++.h>
#define ll long long
#define itn int

using namespace std;

const int maxn=1005;
int dist[maxn];
//从s到i的最短路 
bool vis[maxn];
//每个点有没有求出最短路 
int n,m;
int s,e,d; 
int cnt[1005];//记录每个点 
vector<pair<int,int> > a[maxn];

void add_edge(int s,int e,int d){
    a[s].push_back(make_pair(e,d));
}
void spfa(int s){
    memset(dist,0x3f,sizeof(dist));
    dist[s]=0;
    queue<int> q;
    q.push(s);
    vis[s]=true;
    //最坏O(nm)
    //一般O(km) k 100~200 
    while(q.size()){
        int p=q.front();
        if(cnt[p]>n){
            puts("有负环");
            return;
        }
        q.pop();
        vis[p]=false;
        for(int i=0;i<a[p].size();i++){
            int e=a[p][i].first;
            int d=a[p][i].second;
            if(dist[e]>dist[p]+d){
                dist[e]=dist[p]+d;
                if(!vis[e]){
                    q.push(e);
                    vis[e]=true;
                    cnt[e]++;
                }
            }
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>s>>e>>d;
        add_edge(s,e,d);
    }
    spfa(1);
    return 0;
}

六、生成树

定义：在一个n*n的图里找n-1条边构成一棵树

最小生成树：将边权加起来

1、kruscal

找较小的边权 将所有的边权从小的大排序

并查集：
判断每个点是否连通 因为我们的生成树里面不能有环

代码：

#include <bits/stdc++.h>
using namespace std;
int to[maxn];//to[i] 代表i点在并查集里面的箭头指向谁
int go(int p){//看一下点p沿着并查集箭头最后到底会走到哪里 
    if(to[p] == p) return p;
    else return go(to[p]);
} 
bool cmp(edge a, edge b){
    return a.d<b.d
}
struct edge{
    int s,e,d;
}ed[maxn];//ed[i]代表第i条边是在s与e之间长度为d的边 
int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
        cin >> ed[i].s >> ed[i].e >> ed[i].d;
    sort(ed + 1, ed + m + 1, cmp);//所有边 边权从小到大排序 
    for(int i = 1; i <= n; i++)
        to[i] = i;
    int ans = 0;//生成树大小
    for(int i = 1; i <= m; i++){
        int p1 = ed[i].s , p2 = ed[i].e, d = ed[i].d;
        if(go[p1] != go[p2]){
            ans += d;
            to[go(p1)] = go(p2);
        }
    }
    cout << ans << endl;
    return 0;
}O(nm)

 

优化：

#include <bits/stdc++.h>
using namespace std;
int to[maxn];//to[i] 代表i点在并查集里面的箭头指向谁
int go(int p){//看一下点p沿着并查集箭头最后到底会走到哪里 
    if(to[p] == p) return p;
    //else return to[p] = go(to[p]);
    else{
        int q = go(to[p]);
        to[p] = q;
        return q;
    }
}//O(1)
bool cmp(edge a, edge b){
    return a.d<b.d
}
struct edge{
    int s,e,d;
}ed[maxn];//ed[i]代表第i条边是在s与e之间长度为d的边 
int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
        cin >> ed[i].s >> ed[i].e >> ed[i].d;
    sort(ed + 1, ed + m + 1, cmp);//所有边 边权从小到大排序 
    for(int i = 1; i <= n; i++)
        to[i] = i;
    int ans = 0;//生成树大小
    for(int i = 1; i <= m; i++){
        int p1 = ed[i].s , p2 = ed[i].e, d = ed[i].d;
        if(go[p1] != go[p2]){
            ans += d;
            to[go(p1)] = go(p2);
        }
    }
    cout << ans << endl;
    return 0; 
}//并查集路径压缩 O(mlogm)

次小生成树：

假设最小生成树 只需要删一条边 再加一条边

代码：

#include <bits/stdc++.h>
using namespace std;
vector< int> z[maxn];
void add_edge(int s,int e, int d)//添加一条从s出发 到e 边
{
    //push_back：向vector末尾加入一个元素 
    z[s].push_back(e);
} 
int depth[maxn];//代表每个节点的深度
int f[maxn][20];//f[i][j]代表从i向上走2^j步 会走到哪里 
void dfs(int i,int j)//当前要搜索i点的信息 是从父亲j走到了i 
{
    f[i][0]=j;
    for (int k=1;k<20;k++)
        f[i][k] = f[ f[i][k-1] ][k-1];
    detph[i]=depth[j]+1;
    for (int k=0;k<z[i].size();k++)
    {
        int l=z[i][k];//这条边是从i->l的边
        if (l!=j) dfs(l,i); 
    }
} 

int get_lca(int p1,int p2)//得到p1,p2的lca
//logn
{
    //把p1,p2两个点深度调整成一样的
    if (depth[p1]<depth[p2]) swap(p1,p2);
    for (int i=19;i>=0;i--)
        if (depth[f[p1][i]] >= depth[p2]) p1=f[p1][i]; 
    if (p1==p2) return p1;
    //跳到lca
    for (int i=19;i>=0;i--)
        if (f[p1][i] != f[p2][i]) p1=f[p1][i],p2=f[p2][i];
    return f[p1][0];
} 

int main()
{
    cin >> n >> m;
    for (int i=1;i<=m;i++)
    {
        int s,e;//起点s 终点e
        cin >> s >> e;
        
        add_edge(s,e);
        add_edge(e,s); 
    }
    dfs(1,0);
}
int to[maxn];//to[i] 代表i点在并查集里面的箭头指向谁
int go(int p){//看一下点p沿着并查集箭头最后到底会走到哪里 
    if(to[p] == p) return p;
    else return go(to[p]);
} 
bool cmp(edge a, edge b){
    return a.d<b.d
}
struct edge{
    int s,e,d;
    bool on_tree; 
}ed[maxn];//ed[i]代表第i条边是在s与e之间长度为d的边 
int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
        cin >> ed[i].s >> ed[i].e >> ed[i].d;
    sort(ed + 1, ed + m + 1, cmp);//所有边 边权从小到大排序 
    for(int i = 1; i <= n; i++)
        to[i] = i;
    int ans = 0;//生成树大小
    for(int i = 1; i <= m; i++){
        int p1 = ed[i].s , p2 = ed[i].e, d = ed[i].d;
        if(go[p1] != go[p2]){
            ans += d;
            to[go(p1)] = go(p2);
            add_edge(p1,p2,d);
            add_edge(p2,p1,d);
            edon_tree = true;
        }
        else ed[i].on_tree = fasle;
        dfs(1,0,0);
        int res = 0x3f3f3f3f;
        for(int i = 1; i <= m; i++)
            if(!ed[i].on_tree){
                int p1 = ed[i].s,p2 = ed[i].e, d = ed[i].d;
                res = min(res,ans - get_max(p1, p2 ) + d) ;
                
            }
            cout << res << endl;
    }
    return 0;
}