最短路

最小字典序最短路

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int N =20010,M=N;
int h[N],e[M],ne[M],idx,w[M],dist[N],pre[N],num[N];
int n,m;
bool st[N];
void add(int a,int b,int  c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
void PrintPath(int pre[],int s,int t){
    if(s==t){
        cout<<s;
        return;
    }
    PrintPath(pre,s,pre[t]);
    cout<<"->"<<t;
}
void  spfa() {
    memset(dist,0x3f,sizeof dist);
    dist[0]=0;
    queue<int>q;
    q.push(0);
    st[0]=true;
    while(q.size()){
        int t=q.front();
        q.pop();
        st[t]=false;
        for (int i = h[t]; i != -1; i = ne[i]){
           int j=e[i];
          if (dist[j] > dist[t] + w[i]){
               dist[j]=dist[t]+w[i];
                pre[j]=t;
                num[j]=num[t]+1;
                if(!st[j]){
                    st[j]=true;
                    q.push(j);
                }
            }
            else if (dist[j] == dist[t] + w[i] && num[j] > num[t] + 1) {
                pre[j] = t;
                num[j] = num[t] + 1;
                if (!st[j]) {
                    st[j] = true;
                    q.push(j);
                }
            }
            else if (dist[j] == dist[t] + w[i] && num[j] == num[t] + 1) {
            vector<int>path1;
                int k = j;
                while (k != -1) {
                    path1.push_back(k);
                    k = pre[k];
                }
                reverse(path1.begin(),path1.end());
                vector<int>path2;
                 k = t;
                while (k != -1) {
                    path2.push_back(k);
                    k = pre[k];
                }
                reverse(path2.begin(),path2.end());
                if (path2 < path1) {
                    pre[j] = t;
                    if (!st[j]) {
                        st[j] = true;
                        q.push(j);
                    }
                }
            }

        }
    }
}




int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    memset(pre,-1,sizeof pre);
    for(int i=0;i<m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    spfa();
    for(int i=1;i<n;i++){
        if(dist[i]==0x3f3f3f3f)continue;
        PrintPath(pre,0,i);
        puts("");
    }
    return 0;
}

枚举每个特殊边 两次最短路

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

const int N = 20010,M=N*2;
int ans=1e9;
int n, m,s,t,k;bool flag;
int h[N], w[M], e[M], ne[M], idx;//h表示邻接表 e ne 为边
bool st[N];
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void spfa(int start,vector<int>&dist)
{
    memset(st, 0, sizeof st);
    for(int i=1;i<=n;i++)dist[i]=1e9;
    dist[start] = 0;

    queue<int> q;
    q.push(start);
    st[start] = true;

    while (q.size())
    {
        int t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
}
int main()
{
    while(cin>>n>>s>>t){

        memset(h,-1,sizeof h);
        cin>>m;
        while(m--){
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);add(b,a,c);
        } //建图

        vector<int>dist1(n+1,0);vector<int>dist2(n+1,0);
        spfa(s,dist1);spfa(t,dist2);//分别求出以ts为起点最短路

        cin>>k;//输入地铁个数
        int num=1e9;flag=false;
        ans=dist1[t];
        while(k--){
            int a,b,c;
            cin>>a>>b>>c;
            if((dist1[a]+c+dist2[b]<ans)||(dist1[a]+c+dist2[b]==ans&&a<num&&ans!=dist1[t])){
                flag=true;ans=dist1[a]+c+dist2[b];num=a;
            }
            else if((dist1[b]+c+dist2[a]<ans)||(dist1[b]+c+dist2[a]==ans&&b<num&&ans!=dist1[t])){
                 flag=true;ans=dist1[b]+c+dist2[a];num=b;
            }
        }
        cout<<ans<<endl;
        if(flag)cout<<num<<endl;
        else puts("no metro");
    }
    return 0;
}

Floyd

借用Floyd求强连通分量

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N =210;
int g[N][N];
bool st[N];
int n,ans;
void floyd(){
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++){
        if(g[i][k]&&g[k][j]) g[i][j]=1;
    }
}
int main(){
    int T;
    cin>>T;
    while(T--){
    cin>>n;
    memset(g,0,sizeof g);
    memset(st,0,sizeof st);
    for(int i=1;i<=n;i++){
        int x;
        while(cin>>x&&x!=0)g[i][x]=1;
    }
    floyd();
    ans=0;
    for(int i=1;i<=n;i++){
      if(!st[i]){
          ans++;
          st[i]=true;
          for(int j=1;j<=n;j++){
              if(i==j)continue;
              if(g[i][j]&&g[j][i])st[j]=true;
          }
      }  
    }
    printf("%d\n",ans);
    }
    return 0;
}

Floyd DP求路径数 *

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;double ans;
const int N=110;
int g[N][N];
long long cnt[N][N];
void floyd(){
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
             if(i==j||i==k||j==k)continue;
             if(g[i][j]>g[i][k]+g[k][j]){g[i][j]=g[i][k]+g[k][j];cnt[i][j]=cnt[i][k]*cnt[k][j];} 
                else if(g[i][j]==g[i][k]+g[k][j])cnt[i][j]+=cnt[i][k]*cnt[k][j];
            }
}

int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=g[b][a]=min(g[a][b],c);
        cnt[a][b]=cnt[b][a]=1;
    }
    floyd();
    for(int k=1;k<=n;k++){
        ans=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
        if(i==j||i==k||j==k)continue;
        if(g[i][k]+g[k][j]==g[i][j])
        ans+=g[i][j]*(1.0*cnt[i][k]*cnt[k][j]/cnt[i][j]);
        }
        printf("%.3lf\n",ans);
    }
    return 0;
}

快速排序

#include<iostream>
using namespace std;
const int N =1010;
int a[N],num;
int Partition(int R[], int m, int n){ 
    int K=R[m], L=m+1, G=n; 
    while(L<=G) {
        while(L<=n && R[L]<=K) L++; 
        while(R[G]>K) G--; 
        if(L<G) {swap(R[L],R[G]); L++; G--;}
    }
        swap(R[m],R[G]);
    for(int i=1;i<=num;i++){cout<<R[i]<<" ";}
    cout<<endl;
return G; 
} 
void QuickSort(int R[], int m, int n){ //对Rm…Rn递增排序
if(m <n){
int k=Partition(R, m, n);
QuickSort(R, m, k-1);

QuickSort(R, k+1, n);
}
}
int main(){
    cin>>num;
    for(int i=1;i<=num;i++)cin>>a[i];
    QuickSort(a, 1, num) ;
    for(int i=1;i<=num;i++)cout<<a[i]<<" ";
    return 0;
}

最优树中路径最大权

//2207
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
const int N = 2010, M =30010;
using namespace std;
int n,m,ans,cnt;
int h[N],e[M],ne[M],idx,w[M],p[N],st[N];
void add(int a,int b,int c){
    e[idx]=b;ne[idx]=h[a];w[idx]=c;h[a]=idx++;
}
struct Edge {
    int a, b, w;
    bool operator<(const Edge&W)const {
        return w < W.w;
    }
}edges[M];
int find(int x) {
    if (p[x] != x)p[x] = find(p[x]);
    return p[x];
}

void kruskal(){
    sort(edges,edges+m);
    for(int i=1;i<=n;i++)p[i]=i;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++){

        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a=find(a),b=find(b);
        if(a!=b){
            p[a]=b;
            add(edges[i].a,edges[i].b,edges[i].w);

            add(edges[i].b,edges[i].a,edges[i].w);
        }
    }
}


vector<int>path(n+1,0);
void dfs(int u,int father,int ens){
    if(u==ens){
        for(auto c:path)ans=max(ans,c);
        printf("%d\n",ans);
        return;
    }
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==father)continue;
        path.push_back(w[i]);
        dfs(j,u,ens);
        path.pop_back();
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = { a,b,c };
    }
    kruskal();
    int T;
    cin >> T;
    while (T--) {
       path.clear();
       ans=0;;
       memset(st,0,sizeof st);

        int a, b;
        cin>>a>>b;
        dfs(a,-1,b);

    }

    return 0;
}

//错误原因 建树错误 add写错 数组开小 放入数组参数放错