題目集總目錄
學習指路部落格 圖論

07-圖4 哈利·波特的考試 (25分)

本題鏈接

是很基本的演算法應用，一定要做。如果不會，那麼看看小白專場，會詳細介紹C語言的實現方法

題目大意

給出每兩個動物之間所需魔咒長度
哈利·波特最後應該帶去考場的動物要使得最難變的動物所需總魔咒長度最小。
輸出哈利·波特最後應該帶去考場的動物的編號、以及最長的變形魔咒的長度

思路

用Floyd演算法得出最短路矩陣dist(dist[i][j]表示i到j所需最短長度，在每行裡找最難變(即dist[i][j]最大)的元素，在這些元素中找最小的，輸出最小值的下標i和最小值

程式碼

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 1005;
const int inf  = 0x3f3f3f;
int N,M,x,y,z;
bool visited[maxn];
int dist[maxn][maxn];
//用Floyd演算法得到最短路矩陣
//讓最難變的動物咒語長度最小
void init() {
    for(int i = 1; i <= N; ++i) {
       for(int j = 1; j <= N; ++j) {
            dist[i][j] = inf;
        } 
        dist[i][i] = 0;
    }
}
void Floyd() {
    for(int k = 1; k <= N; ++k) {
        for(int i = 1; i <= N; ++i) {
            for(int j = 1; j <= N; ++j) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}
void solve() {
    int num,ans,hardest;
    ans = inf+1;
    Floyd();
    for(int i = 1; i <= N; ++i) {
        hardest = 0;
        for(int j = 1; j <= N; ++j) {
            if(dist[i][j] > hardest) {
                hardest = dist[i][j];
            }
        }
        if(hardest == inf) {
            printf("0");
            return;
        }
        if(hardest < ans) {
            num = i;
            ans = hardest;
        }
    }
    printf("%d %d\n", num, ans);
}
int main(){
    scanf("%d %d", &N, &M);
    init();
    for(int i = 1; i <= M; ++i) {
        scanf("%d %d %d", &x, &y, &z);
        dist[x][y] = dist[y][x] = z;
    }
    solve();
    return 0;
}

測試點

測試點如下

07-圖5 Saving James Bond - Hard Version (30分)

本題鏈接

有餘力的話，好人做到底，如果上週已經嘗試着救過007了，這周就繼續給他建議吧；

題目大意

輸出最少的跳轉次數以及沿途跳轉的鱷魚的xy座標

思路

用Floyd演算法得出最短路矩陣edge(edge[i][j]表示鱷魚i到鱷魚j所需最少跳轉次數，初始化時能跳轉則置爲1，不能則置爲0），同時用path儲存路徑。
注意一點：如果有許多最短路徑，只需輸出具有最小第一跳轉的路徑

程式碼

// 07-圖5 Saving James Bond - Hard Version (30分)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 105;
const int inf = 0x3f3f3f;
int N,D;
bool vis[maxn];
int edge[maxn][maxn];
int path[maxn][maxn];
struct Point {
    int x, y;
    bool visited;
} v[maxn],s;
struct Fjump{
    int id;
    double d;
    bool operator<(const Fjump& f) {
        return d < f.d;
    }
};
vector<Fjump> fj;
void init() {
    for(int i = 0; i <= N+1; ++i) {
        for(int j = 0; j <= N+1; ++j) {
            edge[i][j] = inf;
            path[i][j] = -1;
        }
        edge[i][i] = 0;
    }
}
double countDist(Point a, Point b) {
    return sqrt(pow((a.x-b.x),2) + pow((a.y-b.y),2));
}
bool check(Point a) {
    int s = 50 - D;
    if(abs(a.x) >= s || abs(a.y) >= s) 
        return true;
    else return false;
}
void Floyd() {
    for(int k = 1; k <= N; ++k) {
        for(int i = 1; i <= N; ++i) {
            for(int j = 1; j <= N; ++j) {
                if(edge[i][k] + edge[k][j] < edge[i][j]) {
                    edge[i][j] = edge[i][k] + edge[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
}
bool firstJump(int i) {
    double d = countDist(s,v[i]);
    d -= 7.5;
    return d <= D;
}
void PrintPath(int S, int E) {
    if(path[S][E] != -1) {
        int k = path[S][E];
        PrintPath(S,k);
        printf("%d %d\n", v[k].x, v[k].y);
        PrintPath(k,E);
    }
}
int main(){
    ios::sync_with_stdio(false);
    scanf("%d %d", &N, &D);
    init();
    v[0].visited = false;
    v[0].x = v[0].y = 0;
    for(int i = 1; i <= N; ++i) {
        scanf("%d %d", &v[i].x, &v[i].y);
        v[i].visited = false;
    }
    for(int i = 1; i <= N; ++i) {
        for(int j = 1; j <= N; ++j) {
            if(countDist(v[i],v[j]) <= D)
                edge[i][j] = edge[j][i] = 1;
        }
    }
    Floyd();
    int mind,temp;
    int S,E;
    mind = inf;
    for(int i = 1; i <= N; ++i) {
        if(firstJump(i)) {
            Fjump f;
            f.d = countDist(s, v[i]);
            f.id = i;
            fj.push_back(f);
        }
    }
    sort(fj.begin(), fj.end());
    for(int i = 0; i < fj.size(); ++i) {
        int sa = fj[i].id;
        if(check(v[sa])) {
                S = sa;
                E = sa;
                mind = 2;
                break;
         }
        for(int j = 1; j <= N; ++j) {
            if(sa == j) continue;
            if(check(v[j])) {
                temp = 2 + edge[sa][j];
                if (temp < mind) {
                    S = sa;
                    E = j;
                    mind = temp;
                }
            }
        }
    }
    if(D >= 42.5) { //一步上岸
        printf("1\n");
    } else if (mind != inf) {
        printf("%d\n", mind);
        if(S == E) {
            printf("%d %d\n", v[S].x, v[S].y);
        } else {
            printf("%d %d\n", v[S].x, v[S].y);
            PrintPath(S,E);
            printf("%d %d\n", v[E].x, v[E].y);
        }
    }  else 
        printf("0\n");
    return 0;
}

測試點

測試點如下

07-圖6 旅遊規劃 (25分)

本題鏈接

Dijkstra演算法的變形——姥姥只能幫你到這裏了，自己動腦筋想一下怎麼改造經典去解決這個問題？實在不會也不要急，再下週會講演算法的。

題目大意

給你所有村莊之間的高速公路距離及其所需花費，計算並輸出給定的兩村莊之間所需最小距離及其花費，若有多條最小路徑則輸出花費最少的。

思路

Dijkstra演算法的變形，只需存邊的時候同時儲存距離及花費，多加一個cost陣列，更新dist時的同時更新cost。

程式碼

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 505;
const int inf  = 0x3f3f3f;
int N,M,S,D,u,v,len,p;
struct Edge {
    int len, pay;
}e[maxn][maxn];
int dist[maxn];
int cost[maxn];
bool vis[maxn];
void init() {
    for(int i = 0; i <= N; ++i) {
        for(int j = 0; j <= N; ++j) {
            e[i][j].pay = e[i][j].len = inf;
        }
        e[i][i].pay = e[i][i].len = 0;
    }
    memset(vis, 0, sizeof(vis));
}
void Dijstra(int u) {
    for(int i = 0; i < N; ++i) {
        dist[i] = e[u][i].len;
        cost[i] = e[u][i].pay;
    }
    for(int i = 1; i <= N; ++i) {
        int t, mindis = inf;
        for(int j = 0; j < N; ++j) {
            if(!vis[j] && dist[j] <= mindis) {
                mindis = dist[j];
                t = j;
            }
        }
        vis[t] = true;
        for(int j = 0; j < N; ++j) {
            if(vis[j] || e[t][j].len == inf) continue;
            if(dist[j] > e[t][j].len + dist[t]) {
                dist[j] = e[t][j].len + dist[t];
                cost[j] = e[t][j].pay + cost[t];
            } else if(dist[j] == e[t][j].len + dist[t]) {
                if(cost[j] > e[t][j].pay + cost[t]) {
                    cost[j] = e[t][j].pay + cost[t];
                }
            }
        }
    }
}
int main(){
    scanf("%d %d %d %d", &N, &M, &S, &D);
    init();
    while(M--) {
        scanf("%d %d %d %d", &u, &v, &len, &p);
        e[u][v].len = e[v][u].len = len;
        e[u][v].pay = e[v][u].pay = p;
    }
    Dijstra(S);
    printf("%d %d\n", dist[D], cost[D]);
    return 0;
}

測試點

測試點如下