WEEK 7作業(yè) A-TT的魔法貓 B-TT的旅行日記 C-TT的美夢

• A-TT的魔法貓
• • 題目描述
  • 輸入輸出格式及樣例
  • 思路
  • 實驗代碼
• B-TT的旅行日記
• • 題目描述
  • 輸入輸出格式及樣例
  • 思路
  • 實驗代碼
• C-TT的美夢
• • 題目描述
  • 輸入輸出格式及樣例
  • 思路
  • 實驗代碼

A-TT的魔法貓

題目描述

眾所周知，TT 有一只魔法貓。
這一天，TT 正在專心致志地玩《貓和老鼠》游戲，然而比賽還沒開始，聰明的魔法貓便告訴了 TT 比賽的最終結(jié)果。TT 非常詫異，不僅詫異于他的小貓咪居然會說話，更詫異于這可愛的小不點為何有如此魔力？
魔法貓告訴 TT，它其實擁有一張游戲勝負(fù)表，上面有 N 個人以及 M 個勝負(fù)關(guān)系，每個勝負(fù)關(guān)系為 A B，表示 A 能勝過 B，且勝負(fù)關(guān)系具有傳遞性。即 A 勝過 B，B 勝過 C，則 A 也能勝過 C。
TT 不相信他的小貓咪什么比賽都能預(yù)測，因此他想知道有多少對選手的勝負(fù)無法預(yù)先得知，你能幫幫他嗎？

輸入輸出格式及樣例

Input
第一行給出數(shù)據(jù)組數(shù)。
每組數(shù)據(jù)第一行給出 N 和 M（N , M <= 500）。
接下來 M 行，每行給出 A B，表示 A 可以勝過 B。
Output
對于每一組數(shù)據(jù)，判斷有多少場比賽的勝負(fù)不能預(yù)先得知。注意 (a, b) 與 (b, a) 等價，即每一個二元組只被計算一次。
Input
3
3 3
1 2
1 3
2 3
3 2
1 2
2 3
4 2
1 2
3 4
Output
0
0
4

思路

??由于勝負(fù)具有傳遞性，a勝過b，b勝過c，那么a就能勝過c，所以本題就是一個求傳遞閉包的過程，使用floyd算法求多源最短路的思想，將最短路的修改改為dis[i][j] = (dis[i][j] | (dis[i][k] & dis[k][j]))，就可以求出每個點對其他點的勝負(fù)情況，因為初始話dis都為false，如果中間點k輸給了i卻贏過了j，則i，j的勝負(fù)關(guān)系就很明朗了，使用與操作就是保證兩者都為1結(jié)果才為1，所以最終二維數(shù)組的表現(xiàn)是，如果dis[i,j]=true，表示i能贏j，false表示不確定，如果dis[i,j],dis[j,i]都為false就表示兩者比賽勝負(fù)不可預(yù)測。求出所有這樣的值除以二即可。

實驗代碼

#include <iostream> #include <cstring> using namespace std; int N, M; bool dis[501][501]; void floyd() {for (int k = 1; k <= N; k++)for (int i = 1; i <= N; i++) {if (dis[i][k]) {for (int j = 1; j <= N; j++)dis[i][j] = (dis[i][j] | (dis[i][k] & dis[k][j]));}} } int main(){int n;cin >> n;while (n > 0) {cin >> N >> M;memset(dis, false, sizeof(dis));int a, b;for (int i = 0; i < M; i++) {cin >> a >> b;dis[a][b] = true;}floyd();int count = 0;for (int i = 1; i <= N; i++)for (int j = i + 1; j <= N; j++)if (dis[i][j] == false && dis[j][i] == false)count++;cout << count << endl;n--;}return 0; }

---

B-TT的旅行日記

題目描述

眾所周知，TT 有一只魔法貓。
今天他在 B 站上開啟了一次旅行直播，記錄他與魔法貓在喵星旅游時的奇遇。 TT 從家里出發(fā)，準(zhǔn)備乘坐貓貓快線前往喵星機(jī)場。貓貓快線分為經(jīng)濟(jì)線和商業(yè)線兩種，它們的速度與價錢都不同。當(dāng)然啦，商業(yè)線要比經(jīng)濟(jì)線貴，TT 平常只能坐經(jīng)濟(jì)線，但是今天 TT 的魔法貓變出了一張商業(yè)線車票，可以坐一站商業(yè)線。假設(shè) TT 換乘的時間忽略不計，請你幫 TT 找到一條去喵星機(jī)場最快的線路，不然就要誤機(jī)了！

輸入輸出格式及樣例

Input
輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)第一行為 3 個整數(shù) N, S 和 E (2 ≤ N ≤ 500, 1 ≤ S, E ≤ 100)，即貓貓快線中的車站總數(shù)，起點和終點（即喵星機(jī)場所在站）編號。
下一行包含一個整數(shù) M (1 ≤ M ≤ 1000)，即經(jīng)濟(jì)線的路段條數(shù)。
接下來有 M 行，每行 3 個整數(shù) X, Y, Z (1 ≤ X, Y ≤ N, 1 ≤ Z ≤ 100)，表示 TT 可以乘坐經(jīng)濟(jì)線在車站 X 和車站 Y 之間往返，其中單程需要 Z 分鐘。
下一行為商業(yè)線的路段條數(shù) K (1 ≤ K ≤ 1000)。
接下來 K 行是商業(yè)線路段的描述，格式同經(jīng)濟(jì)線。
所有路段都是雙向的，但有可能必須使用商業(yè)車票才能到達(dá)機(jī)場。保證最優(yōu)解唯一。
Output
對于每組數(shù)據(jù)，輸出3行。第一行按訪問順序給出 TT 經(jīng)過的各個車站（包括起點和終點），第二行是 TT 換乘商業(yè)線的車站編號（如果沒有使用商業(yè)線車票，輸出"Ticket Not Used"，不含引號），第三行是 TT 前往喵星機(jī)場花費(fèi)的總時間。
本題不忽略多余的空格和制表符，且每一組答案間要輸出一個換行
Input
4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3
Output
1 2 4
2
5

思路

本題是基于圖的問題，由于涉及到權(quán)值為題，我們建立鏈?zhǔn)角跋蛐敲枋鰣D，本題如果沒有商業(yè)線，就是一個單純的求最短路的問題，加了商業(yè)線就不同的，因為商業(yè)線的乘坐次數(shù)有限，本題只限一次，所以我們可以用兩次dijkstra算法求出源點到各點，終點到各點的最短距離，然后遍歷每一條商業(yè)線，將起點到商業(yè)線的其中一個端點的距離，加上終點到另一個端點的距離，加上商業(yè)線的權(quán)值，就可以得出使用商業(yè)線的距離，由于本題是無向圖，所以要交換端點再求一次，這樣求出使用該商業(yè)線的最短距離，再與不用商業(yè)線的最短距離進(jìn)行比較，使用小的，將商業(yè)線遍歷完就可以得到最短路。
但最后要注意輸出路徑的時候，前半段是源點到中間點，后半段是終點到中間點，如果使用的是pre數(shù)組要倒著輸出。

實驗代碼

#include <iostream> #include <stdio.h> #include <cstring> #include <queue> #include <vector> using namespace std; const int inf = 101; const int maxn = 500; int n, N, S, E, M, K; struct Edge {//邊//int u;int v;int w;int nxt; }edge[maxn * maxn]; int head[maxn], tot;//鏈?zhǔn)角跋蛐?/span> void init() {tot = 0;memset(head, -1, sizeof(head)); } void add(int u, int v, int w) {edge[++tot].v = v;edge[tot].w = w;edge[tot].nxt = head[u];head[u] = tot; } int vis[maxn]; priority_queue<pair<int, int> > q; void dijkstra(int s,int* dis,int *path) {while (q.size()) q.pop();memset(vis, 0, sizeof(vis));for (int i = 1; i <= N; i++) dis[i] = inf;dis[s] = 0;q.push(make_pair(0, s));while (q.size() ) {int x = q.top().second;q.pop();if (vis[x]) continue;vis[x] = 1;for (int i = head[x]; i != -1; i = edge[i].nxt) {int y = edge[i].v, W = edge[i].w;if (dis[y] > dis[x] + W) {path[y] = x;dis[y] = dis[x] + W;q.push(make_pair(-dis[y], y));}}} } int dis1[maxn], dis2[maxn], path1[maxn], path2[maxn]; int main(){while (cin >> N >> S >> E) {cin >> M;init();int u, v, w;for (int i = 0; i < M; i++) {scanf("%d%d%d", &u, &v, &w);add(u, v, w);add(v, u, w);}for (int i = 0; i <= N; i++) {dis1[i] = 0; dis2[i] = 0; path1[i] = 0; path2[i] = 0;}dijkstra(S, dis1, path1); dijkstra(E, dis2, path2);int k; cin >> k;int min = dis1[E], temp = 1, temp1 = 0, temp2 = 0; ; for (int i = 0; i < k; i++) {scanf("%d%d%d", &u, &v, &w);int sum = dis1[u] + dis2[v] + w;if (min > sum) {min = sum; temp1 = u; temp2 = v; temp = 0;}sum = dis1[v] + dis2[u] + w;if (min > sum) {min = sum; temp1 = v; temp2 = u; temp = 0;}}vector<int> path;int i = temp1;if (temp == 0) {path.push_back(temp1);if (temp1 != S) {while (path1[i] != S) {path.insert(path.begin(), path1[i]);i = path1[i];}path.insert(path.begin(), path1[i]);}path.push_back(temp2); i = temp2;if (temp2 != E) {while (path2[i] != E) {path.push_back(path2[i]);i = path2[i];}path.push_back(E);}int n = path.size();for (int i = 0; i < n; i++)cout << path[i] << " ";cout << endl;cout << temp1 << endl;}else {cout << S << " "; i = S;while (path2[i] != E) {cout << path2[i] << " ";i = path2[i];}cout << E << endl;cout << "Ticket Not Used" << endl;}cout << min << endl << endl;}return 0; }

---

C-TT的美夢

題目描述

這一晚，TT 做了個美夢！
在夢中，TT 的愿望成真了，他成為了喵星的統(tǒng)領(lǐng)！喵星上有 N 個商業(yè)城市，編號 1 ～ N，其中 1 號城市是 TT 所在的城市，即首都。
喵星上共有 M 條有向道路供商業(yè)城市相互往來。但是隨著喵星商業(yè)的日漸繁榮，有些道路變得非常擁擠。正在 TT 為之苦惱之時，他的魔法小貓咪提出了一個解決方案！TT 欣然接受并針對該方案頒布了一項新的政策。
具體政策如下：對每一個商業(yè)城市標(biāo)記一個正整數(shù)，表示其繁榮程度，當(dāng)每一只喵沿道路從一個商業(yè)城市走到另一個商業(yè)城市時，TT 都會收取它們（目的地繁榮程度 - 出發(fā)地繁榮程度）^ 3 的稅。
TT 打算測試一下這項政策是否合理，因此他想知道從首都出發(fā)，走到其他城市至少要交多少的稅，如果總金額小于 3 或者無法到達(dá)請悄咪咪地打出 ‘?’。

輸入輸出格式及樣例

Input
第一行輸入 T，表明共有 T 組數(shù)據(jù)。（1 <= T <= 50）
對于每一組數(shù)據(jù)，第一行輸入 N，表示點的個數(shù)。（1 <= N <= 200）
第二行輸入 N 個整數(shù)，表示 1 ～ N 點的權(quán)值 a[i]。（0 <= a[i] <= 20）
第三行輸入 M，表示有向道路的條數(shù)。（0 <= M <= 100000）
接下來 M 行，每行有兩個整數(shù) A B，表示存在一條 A 到 B 的有向道路。
接下來給出一個整數(shù) Q，表示詢問個數(shù)。（0 <= Q <= 100000）
每一次詢問給出一個 P，表示求 1 號點到 P 號點的最少稅費(fèi)。
Output
每個詢問輸出一行，如果不可達(dá)或稅費(fèi)小于 3 則輸出 ‘?’。
Input
2
5
6 7 8 9 10
6
1 2
2 3
3 4
1 5
5 4
4 5
2
4
5
10
1 2 4 4 5 6 7 8 9 10
10
1 2
2 3
3 1
1 4
4 5
5 6
6 7
7 8
8 9
9 10
2
3 10
Output
Case 1:
3
4
Case 2:
？
？

思路

先引入spfa算法，spfa算法是可以解決邊權(quán)值為負(fù)值單源最短路，思想我覺得和前序遍歷有點相似，從起點開始入隊列，然后將他的鄰接點入隊列，保證每個點只入隊列一次，每次出隊列，期間不斷更新起點到隊首元素鄰接點的距離為最短，方法是起點到隊首元素的距離加上該邊權(quán)值就是起點到隊首元素鄰接點的距離，為了保證最短，每次加上判斷即可，同時還有一個數(shù)組記錄，起點到每個點最短距離所經(jīng)過的點數(shù)，如果點數(shù)大于了總點數(shù)，說明這里出現(xiàn)了負(fù)環(huán)，也就是權(quán)值和為負(fù)數(shù)的環(huán)導(dǎo)致求最短距離的時候在環(huán)里面繞，對于這種情況說明求不出到該點的最短距離，執(zhí)行相應(yīng)的處理工作即可。
本題就是一個spfa算法的例子，本題的邊權(quán)是兩者的差，沒有給出兩者的大小，所以可能是負(fù)數(shù)，所以本題采用spfa算法，，由于本題要求不能到達(dá)的點，也就是求負(fù)環(huán)里面的點，我們求出一個負(fù)環(huán)里面的點，然后對他進(jìn)行dfs即可。

實驗代碼

#include <iostream> #include <algorithm> #include <queue> using namespace std; const int inf = 100000; const int maxn = 200; int inq[maxn], cnt[maxn], dis[maxn]; struct Edge {//邊int v;int w;int nxt; }edge[1000000]; int head[maxn], tot; void add(int u, int v, int w){edge[++tot].v = v;edge[tot].w = w;edge[tot].nxt = head[u];head[u] = tot; } int vis[maxn]; void dfs(int s){for (int i = head[s]; i != -1; i = edge[i].nxt){int y = edge[i].v;if (!vis[y]){vis[y] = 1;dfs(y);}} } void spfa(int s, int n){queue<int> q;for (int i = 1; i <= n; i++){inq[i] = 0;cnt[i] = 0;dis[i] = inf;}dis[s] = 0;inq[s] = 1;q.push(s);while (!q.empty()){int u = q.front();q.pop();inq[u] = 0;for (int i = head[u]; i!=-1; i = edge[i].nxt){int v = edge[i].v;int w = edge[i].w;if (dis[v] > dis[u] + w){cnt[v] = cnt[u] + 1;if (cnt[v] >= n){dfs(v); continue;}dis[v] = dis[u] + w;if (!inq[v]){q.push(v);inq[v] = 1;}}}} }int main(){//cin.sync_with_stdio(false);int T;cin >> T;int count = 1;while (T--){int n; cin >> n;tot = 1;for (int i = 1; i <= n; i++) {vis[i] = false;head[i] = -1;}int* a = new int[n + 1];for (int i = 1; i <= n; i++)cin >> a[i];int m; cin >> m;for (int i = 0; i < m; i++){int b, c;cin >> b >> c;int w = (a[c] - a[b]) * (a[c] - a[b]) * (a[c] - a[b]);add(b, c, w);}spfa(1, n);int Q; cin >> Q;cout << "Case " << count <<":"<< endl; count++;for (int i = 0; i < Q; i++){int p; cin >> p;if (dis[p] == inf || vis[p] || dis[p] < 3)cout << "?" << endl;elsecout << dis[p] << endl;}}return 0; }

---

總結(jié)

以上是生活随笔為你收集整理的WEEK 7作业 A-TT的魔法猫 B-TT的旅行日记 C-TT的美梦的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。