首頁 程式語言筆記 C++ 基礎演算法

# 最短路徑

BFS 可以求得短的路徑長，只不過呢，他只能就權值一樣的最短路，也就是說，每條路都一樣長的狀況才能用。
現在，給你一張地圖，且這張圖有了每條邊的長度不盡相同，不能再用 BFS 的話，就要嘗試接下來的演算法囉

# Floyd-Warshall

# 想法

Floyd-Warshall 是尋找最短路徑的一種方式，算是超簡單有好用的一種，主要是處理全圖的最短 (最長) 路徑。
換句話說，用這個方法處理過一次就可以輕鬆取得任意兩點的距離了，甚至還可以處理負邊。
只不過...，他超慢就是了 QQ

# 作法

作法也很簡單就是，抄捷徑而已，每次窮舉兩個點只要中間有一個點可以更符合題意的路徑，就更新為那個路徑。
如果是尋找最短路徑，式子大概長這樣 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j])
相對的如果是尋找最長路徑的話，就會是dis[i][j]=max(dis[i][j],dis[i][k]+dis[k][j]dis[i][j] = max(dis[i][j],dis[i][k]+dis[k][j]
三層 for 迴圈就能輕鬆做到囉

# d908: 4. 最佳路徑

# 內容

給你一個有向圖，輸出擁有最大權重總和的路徑之權重總和值。

# 思路

就是一題超基本的 floyd-warshall 而已

# 程式碼

#include <bits/stdc++.h>
using namespace std;
int n;
int d[101][101];
int main(){
   char c;int i, j;
   while(cin>>c>>n){
      int w,m=0;
      char a ,b;
      memset(d,0,sizeof(d));
        for (i = 0; i < n; ++i) {
            cin>>a>>b>>w;
            if(w > d[a-'A'][b-'A']) d[a-'A'][b-'A']=w;
        }
        for (int k = 0; k < n; ++k) {
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    if ((d[i][k] * d[k][j] != 0) && (i != j))
                            d[i][j] = max(d[i][j], d[i][k] + d[k][j]);
        }
        for (j = 0; j < n; ++j)  m=max(m,d[c-'A'][j]);
        cout<<m<<endl;
   }
   return 0;
}
# a674: 10048 - Audiophobia
# 內容
就是要你求 A 到 B 點途中的最小值
# 思路
一樣是窮舉兩點，找中間那點，只不過式子會變成這樣
d[i][j]=d[j][i]=min(d[i][j],max(d[i][k],d[k][j]))d[i][j] = d[j][i] = min(d[i][j],max(d[i][k],d[k][j]))
# 程式碼
#include <bits/stdc++.h>
using namespace std;
int d[101][101];
int c,s,q,idx = 0;
int x,y;
int main() {
    while(cin>>c>>s>>q&&(c||s||q)&&++idx){
        memset(d,0x3f,sizeof(d));
        for(int i = 0;i<26;i++)d[i][i]=0;
        for(int i =0,t;i<s;i++){
            cin>>x>>y>>t; d[x][y] = d[y][x] = t;
        }
        for(int k = 1;k<=100;k++)for(int i = 1;i<=100;i++)for(int j = 1;j<=100;j++)
            d[i][j] = d[j][i] = min(d[i][j],max(d[i][k],d[k][j]));
        cout<<"Case #"<<idx<<'\n';
        for(int i = 0;i<q;i++){
            cin>>x>>y;
            if(d[x][y]>400000) cout<<"no path\n";
            else cout<<d[x][y]<<'\n';
        }
    }
}
# c128: Heavy Cargo
# 內容
求 A 到 B 途中的最大值
# 解題思路
一樣是窮舉兩點，找中間那點，只不過式子會變成這樣
d[i][j]=d[j][i]=max(d[i][j],min(d[i][k],d[k][j]))d[i][j] = d[j][i] = max(d[i][j],min(d[i][k],d[k][j]))
#include <bits/stdc++.h>
using namespace std;
 
map <string, int> mp;
int idx, cnt = 0;
int a[205][205];
 
int getid(string str){
    if (mp.count(str)) return mp[str];
    else{
        mp[str] = idx; idx++;
        return mp[str];
    }
}
 
int main() {
    int n, r;
    while (cin >> n >> r&&++cnt){
        if (n == 0) break;
        idx = 0; mp.clear();
        memset(a, -1, sizeof(a));
        string s1, s2;
        int temp, n1, n2;
        for (int i = 0; i < r; i++){
            cin >> s1 >> s2 >> temp;
            n1 = getid(s1),n2 = getid(s2);
            a[n1][n2] = a[n2][n1] = temp;
        }
        cin >> s1 >> s2;
        n1 = getid(s1); n2 = getid(s2);
        //Floyd-Warshall
        for (int i = 0; i < n; i++)for(int j = 0; j < n-1; j++)for (int k = j+1; k < n; k++)
            a[j][k] = a[k][j] = max(a[j][k], min(a[j][i], a[i][k]));
        printf("Scenario #%d\n%d tons\n", cnt, a[n1][n2]);
    }
}
# Dijkstra
# 想法
是解決單源最短路問題 (SSSP) 問題的常用方式，
從一個指定的點開始向外拓張，連結的下一個點權重即為自己當前的權重加上路徑長
如果下一個點已經有標記權重了，就更新為比較小的那一個值，直到都跑完為止
其演示在此:
# 作法
  1. n-1 次循環
  2. 找到偽標記的 d 最小點
  3. 標記，並鬆弛 (更新) 他的邊
# heap 優化
用 STL 中的優先隊列 (priority_queue) 實現：
while (優先隊列非空){
提出隊頭，鬆弛他的邊
鬆弛了的 <新距離，點> 入隊
}
# 程式碼
typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,greater<PII> > q;
...
while(!q.empty()){  
    int w=q.top().first, u=q.top().second;
    q.pop();   
    if(b[u])continue; b[u]=true;
    for(int i=head[u];i;i=e[i].next){ 
        int v=e[i].to;
        if(d[u]+e[i].w<d[v]){
            d[v]=d[u]+e[i].w;
            q.push(PII(d[v],v));  
        }
    }
}
# 例題 d793-acm-929-NumberMaze
# 內容
數字迷宮為一個二維的數字 (0-9) 陣列。你可以用直角方向 (東、西、南、北) 在迷宮中尋訪。假設每一格的數字代表造訪該格的成本，那麼求出從入口走到出口所需的最小成本不見得很容易哦。
# 思路
把這個二為陣列想像成一個無項圖，每個格子與四個方格連接。然後在實作 Dijkstra 就好了
# 程式碼
#include <bits/stdc++.h>
#define MAX 1000
using namespace std;
int Map[MAX][MAX],dp[MAX][MAX],v[MAX][MAX];
int mv[4][2]=<!--swig0-->;
typedef struct node{
  int x,y,dis;
  bool operator<(const node& mynode) const{
    return (mynode.dis < dis);
  }
}Node;
int main(){
    int ncase,n,m;
    priority_queue <Node> pq;
    Node mynode;
    cin >> ncase;
    for(int m=0;m<ncase;m++){
        while (cin >> n >> m){
        memset(v,0,sizeof(v));
        for(int i=0;i<n;i++) for(int j=0;j<m;j++)  dp[i][j]=199999999;
        for(int i=0;i<n;i++) for(int j=0;j<m;j++)  cin >> Map[i][j];
        mynode.x=0,mynode.y=0;
        dp[0][0]=mynode.dis=Map[0][0];
        pq.push(mynode);
        while(!pq.empty()){
            mynode=pq.top(); pq.pop();
            v[mynode.y][mynode.x]=1;
            for(int i=0;i<4;i++){
                Node tmp;
                int nowx = mynode.x+mv[i][0],nowy = mynode.y+mv[i][1];
                if ((nowx<0)||(nowx>=m)) continue;
                if ((nowy<0)||(nowy>=n)) continue;
                if (v[nowy][nowx]==0){
                    if (dp[nowy][nowx]>(dp[nowy][nowx]+Map[nowy][nowx])) {
                        dp[nowy][nowx]=dp[mynode.y][mynode.x]+Map[nowy][nowx];
                        tmp.x=nowx,tmp.y=nowy;
                        tmp.dis=dp[nowy][nowx];
                        pq.push(tmp);
                    }
                }
            }
      }
      cout << dp[n-1][m-1] << endl;
    }
  }
}
# SPFA
# 想法
一樣是求單源最短路問題 (SSSP) 的方法，是 Bellman-Ford 的優化，Bellman-Ford: 每次對所有的邊鬆弛。可以計算出有負邊無負環的最短路，並且可以判斷是否存在負環。
# 作法
起點 push 到 queue 裡面
while (優先隊列非空){
提出隊頭，鬆弛他的邊
把所有被更新到的點都 push 到 queue 裡面
}
# 程式碼
while(!q.empty()){
    int u=q.front(); q.pop();
    b[u]=false;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(d[u]+e[i].w<d[v]){
            d[v]=d[u]+e[i].w;
            if(!b[v])b[v]=true,q.push(v);
        }
    }
}
# 例題 c125: 00534 - Frogger
# 內容
給你 Freddy 所在的石頭、Fiona 所在的石頭，以及湖中所有其他石頭的座標，你的任務是算出介於 Freddy 和 Fiona 所在石頭間的蛙跳距離。
# 想法
明顯是一個基本的 SSSP 問題，所以直接運用 SPFA 的方式解決吧！
從起點到終點的每條路都有一個石頭間最大距離，
在每條路的石頭間最大距離中，找最小值。
(也可以使用 Dijkstra 解決喔～～
#include<bits/stdc++>
#define N 201
using namespace std;
struct Coord{
    int x, y;
    float getDistance(Coord& a){
        return sqrt((x - a.x)*(x - a.x) + (y - a.y)*(y - a.y));
    }
}stone[N];
float SPFA(int n);
int main() {
    int n, i, Case = 1;
    while (scanf("%d", &n) && n) {
        // 第 0 和 1 分別為起點和終點
        for (i = 0; i < n; i++)
            scanf("%d%d", &stone[i].x, &stone[i].y);
        printf("Scenario #%d\nFrog Distance = %.3f\n\n", Case++, SPFA(n));
    }
    return 0;
}
float SPFA(int n) {
    int i;
    float d[N] = { 0 };
    bool inQ[101] = {};
    queue<int> Q;
    for (i = 1; i < n; i++)  d[i] = 1e9;
    Q.push(0);
    while (!Q.empty()) {
        int idx = Q.front(), Q.pop();
        inQ[idx] = false;
        for (i = 1; i < n; i++) {
            float max = max(d[idx], stone[idx].getDistance(stone[i]));
            
            if (max < d[i]) {
                d[i] = max;
                if (!inQ[i]) Q.push(i), inQ[i] = true;
            }
        }
    }
    return d[1];
}
# 附註
如果是稠密圖，Dijkstra+heap 比 SPFA 快。
稀疏圖則 SPFA 更快。 SPFA 可以有 SLF 和 LLL 兩種優化，SLF 就是 d 比隊頭小就插入隊頭，否則插入隊尾。
   
 更新於   閱讀次數  次
用實際行動犒賞爆肝的我😀
Zrn Ye LinePay
LinePay