A - TT 的魔法貓

題意：

眾所周知，TT 有一只魔法貓。

這一天，TT 正在專心致志地玩《貓和老鼠》游戲，然而比賽還沒(méi)開(kāi)始，聰明的魔法貓便告訴了 TT 比賽的最終結(jié)果。TT 非常詫異，不僅詫異于他的小貓咪居然會(huì)說(shuō)話，更詫異于這可愛(ài)的小不點(diǎn)為何有如此魔力？

魔法貓告訴 TT，它其實(shí)擁有一張游戲勝負(fù)表，上面有 N 個(gè)人以及 M 個(gè)勝負(fù)關(guān)系，每個(gè)勝負(fù)關(guān)系為 A B，表示 A 能勝過(guò) B，且勝負(fù)關(guān)系具有傳遞性。即 A 勝過(guò) B，B 勝過(guò) C，則 A 也能勝過(guò) C。

TT 不相信他的小貓咪什么比賽都能預(yù)測(cè)，因此他想知道有多少對(duì)選手的勝負(fù)無(wú)法預(yù)先得知，你能幫幫他嗎？

Input

第一行給出數(shù)據(jù)組數(shù)。

每組數(shù)據(jù)第一行給出 N 和 M（N , M <= 500）。

接下來(lái) M 行，每行給出 A B，表示 A 可以勝過(guò) B。

Output

對(duì)于每一組數(shù)據(jù)，判斷有多少場(chǎng)比賽的勝負(fù)不能預(yù)先得知。注意 (a, b) 與 (b, a) 等價(jià)，即每一個(gè)二元組只被計(jì)算一次。

Sample Input

3 3 3 1 2 1 3 2 3 3 2 1 2 2 3 4 2 1 2 3 4

Sample Output

0 0 4

思路做法：

這是經(jīng)過(guò)變化后的多源最短路算法問(wèn)題，將原問(wèn)題轉(zhuǎn)化為圖的問(wèn)題，即為若A勝過(guò)B，則A到B有一條邊，由于點(diǎn)數(shù)不多，可以用鄰接矩陣存儲(chǔ)。根據(jù)規(guī)則，把多源最短路算法中的更新改變?yōu)門(mén)T[i][j] = TT[i][j] | TT[i][k]&TT[k][j]并且為了降低復(fù)雜度，需要剪枝避免不必要的計(jì)算，即先判斷TT[i][k]是否為true，若否則一定不能更新，直接跳過(guò)。最后便歷矩陣，若TT[i][j]和TT[j][i]都為false則勝負(fù)未知否則若其中一個(gè)為true則勝負(fù)已分，不可能出現(xiàn)2個(gè)都是true的情況，同時(shí)將矩陣清零以進(jìn)行下一輪。

總結(jié):

正常情況下不可能直接給出原始問(wèn)題來(lái)求解，大多是多源最短路算法的變體。

代碼:

#include <stdio.h>const int N = 500+5; bool TT[N][N];int main(){int t; scanf("%d", &t);while(t--){int n, m, ans = 0; scanf("%d %d", &n, &m);for(int i = 0; i < m; ++i){int a, b; scanf("%d %d", &a, &b);TT[a][b] = 1;}for(int k = 1; k <= n; ++k){for(int i = 1; i <= n; ++i){if(TT[i][k]){for(int j = 1; j <= n; ++j){TT[i][j] = TT[i][j] | TT[i][k]&TT[k][j];}}}}for(int i = 1; i <= n; ++i){for(int j = i+1; j <= n; ++j){if(!TT[i][j]&&!TT[j][i]) ans++; TT[i][j] = 0; TT[j][i] = 0;}}printf("%d\n", ans);}return 0; }

B - TT 的旅行日記

題意：

眾所周知，TT 有一只魔法貓。

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

Input

輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)第一行為 3 個(gè)整數(shù) N, S 和 E (2 ≤ N ≤ 500, 1 ≤ S, E ≤ 100)，即貓貓快線中的車(chē)站總數(shù)，起點(diǎn)和終點(diǎn)（即喵星機(jī)場(chǎng)所在站）編號(hào)。

下一行包含一個(gè)整數(shù) M (1 ≤ M ≤ 1000)，即經(jīng)濟(jì)線的路段條數(shù)。

接下來(lái)有 M 行，每行 3 個(gè)整數(shù) X, Y, Z (1 ≤ X, Y ≤ N, 1 ≤ Z ≤ 100)，表示 TT 可以乘坐經(jīng)濟(jì)線在車(chē)站 X 和車(chē)站 Y 之間往返，其中單程需要 Z 分鐘。

下一行為商業(yè)線的路段條數(shù) K (1 ≤ K ≤ 1000)。

接下來(lái) K 行是商業(yè)線路段的描述，格式同經(jīng)濟(jì)線。

所有路段都是雙向的，但有可能必須使用商業(yè)車(chē)票才能到達(dá)機(jī)場(chǎng)。保證最優(yōu)解唯一。

Output

對(duì)于每組數(shù)據(jù)，輸出3行。第一行按訪問(wèn)順序給出 TT 經(jīng)過(guò)的各個(gè)車(chē)站（包括起點(diǎn)和終點(diǎn)），第二行是 TT 換乘商業(yè)線的車(chē)站編號(hào)（如果沒(méi)有使用商業(yè)線車(chē)票，輸出"Ticket Not Used"，不含引號(hào)），第三行是 TT 前往喵星機(jī)場(chǎng)花費(fèi)的總時(shí)間。

本題不忽略多余的空格和制表符，且每一組答案間要輸出一個(gè)換行

Sample Input

4 1 4 4 1 2 2 1 3 3 2 4 4 3 4 5 1 2 4 3

Sample Output

1 2 4 2 5

思路做法：

單源最短路算法的變體問(wèn)題，不能直接使用原算法。除帶有動(dòng)態(tài)規(guī)劃的思想算法求解外，較容易理解的是針對(duì)每條商業(yè)線（i，j）便歷，分別計(jì)算（s，i）+（i，j）+（j，e）的值并最小化，最后與不走商業(yè)線的方案取最小值（不一定用到商業(yè)線的就是最小的）。因此具體做法為從s開(kāi)始運(yùn)行一遍最短路算法，再?gòu)膃開(kāi)始運(yùn)行一遍最短路算法，然后便歷每一條商業(yè)線，為求最小值不斷更新記錄的相關(guān)參數(shù)，最后與dis1[e]（不走商業(yè)線的結(jié)果）比較，并遞歸輸出路徑上的結(jié)點(diǎn)。

總結(jié):

運(yùn)用逐個(gè)便歷商業(yè)線的思想寫(xiě)起代碼還是不難的，還有值得注意的一點(diǎn)是題目中要求的輸出格式，最后不能有多與的空格，這里用變量t記錄次數(shù)實(shí)現(xiàn)。

代碼:

#include <stdio.h> #include <vector> #include <queue> using namespace std; const int N = 500+5; const int M = 1000+5; const int K = 1000+5; const int INF = 0x3f3f3f3f; struct Edge{int v, w;Edge(){}Edge(int _v, int _w):v(_v), w(_w){} }; vector<Edge> E[N]; struct Point{int p, d;Point(){}Point(int _p, int _d):p(_p), d(_d){}bool operator<(const Point& P) const {return d < P.d;} }; int pre1[N], pre2[N], vis[N], dis1[N], dis2[N]; priority_queue<Point> q; void addEdge(int u, int v, int w){E[u].push_back(Edge(v, w));E[v].push_back(Edge(u, w)); } void dijkstra(int s, int e, int n, int *dis, int *pre){while(!q.empty()) q.pop();for(int i = 1; i <= n; ++i){pre[i] = 0; vis[i] = 0;dis[i] = INF;}dis[s] = 0; q.push(Point(s, 0));while(!q.empty()){int u = q.top().p; q.pop();if(vis[u]){if(u == e) return;continue;}vis[u] = 1;for(int i = 0, len = E[u].size(); i < len; ++i){int v = E[u][i].v, w = E[u][i].w;if(vis[v]) continue;if(dis[v] > dis[u] + w){dis[v] = dis[u] + w; pre[v] = u;q.push(Point(v, -dis[v]));}}} } void output1(int s, int e, int *pre){if(e == s) return;output1(s, pre[e], pre);printf(" %d", e); } void output2(int s, int e, int *pre){if(e == s) return;printf(" %d", pre[s]);output2(pre[s], e, pre); } int main(){int n, s, e, t = 0;while(~scanf("%d%d%d", &n, &s, &e)){for(int i = 1; i <= n; ++i)while(!E[i].empty()) E[i].pop_back();int x, y, z;int m; scanf("%d", &m); //經(jīng)濟(jì)線 for(int i = 0; i < m; ++i){scanf("%d%d%d", &x, &y, &z);addEdge(x, y, z);}dijkstra(s, e, n, dis1, pre1); dijkstra(e, s, n, dis2, pre2);int cost = dis1[e], temp = cost, u = 0, v = 0;int k; scanf("%d", &k); //商業(yè)線for(int i = 0; i < k; ++i){scanf("%d%d%d", &x, &y, &z);int cost1 = dis1[x] + dis2[y] + z;int cost2 = dis1[y] + dis2[x] + z;if(cost1 < cost2 && cost1 < cost){cost = cost1; u = x; v = y;}else if(cost2 < cost1 && cost2 < cost){cost = cost2; u = y; v = x;}}if(t) printf("\n");if(temp > cost){printf("%d", s); output1(s, u, pre1);printf(" %d", v); output2(v, e, pre2);printf("\n%d\n%d\n", u, cost);}else{printf("%d", s); output1(s, e, pre1);printf("\nTicket Not Used\n%d\n", dis1[e]);}t++;}return 0; }

C - TT 的美夢(mèng)

題意：

這一晚，TT 做了個(gè)美夢(mèng)！

在夢(mèng)中，TT 的愿望成真了，他成為了喵星的統(tǒng)領(lǐng)！喵星上有 N 個(gè)商業(yè)城市，編號(hào) 1 ～ N，其中 1 號(hào)城市是 TT 所在的城市，即首都。

喵星上共有 M 條有向道路供商業(yè)城市相互往來(lái)。但是隨著喵星商業(yè)的日漸繁榮，有些道路變得非常擁擠。正在 TT 為之苦惱之時(shí)，他的魔法小貓咪提出了一個(gè)解決方案！TT 欣然接受并針對(duì)該方案頒布了一項(xiàng)新的政策。

具體政策如下：對(duì)每一個(gè)商業(yè)城市標(biāo)記一個(gè)正整數(shù)，表示其繁榮程度，當(dāng)每一只喵沿道路從一個(gè)商業(yè)城市走到另一個(gè)商業(yè)城市時(shí)，TT 都會(huì)收取它們（目的地繁榮程度 - 出發(fā)地繁榮程度）^ 3 的稅。

TT 打算測(cè)試一下這項(xiàng)政策是否合理，因此他想知道從首都出發(fā)，走到其他城市至少要交多少的稅，如果總金額小于 3 或者無(wú)法到達(dá)請(qǐng)悄咪咪地打出 ‘?’。

Input

第一行輸入 T，表明共有 T 組數(shù)據(jù)。（1 <= T <= 50）

對(duì)于每一組數(shù)據(jù)，第一行輸入 N，表示點(diǎn)的個(gè)數(shù)。（1 <= N <= 200）

第二行輸入 N 個(gè)整數(shù)，表示 1 ～ N 點(diǎn)的權(quán)值 a[i]。（0 <= a[i] <= 20）

第三行輸入 M，表示有向道路的條數(shù)。（0 <= M <= 100000）

接下來(lái) M 行，每行有兩個(gè)整數(shù) A B，表示存在一條 A 到 B 的有向道路。

接下來(lái)給出一個(gè)整數(shù) Q，表示詢問(wèn)個(gè)數(shù)。（0 <= Q <= 100000）

每一次詢問(wèn)給出一個(gè) P，表示求 1 號(hào)點(diǎn)到 P 號(hào)點(diǎn)的最少稅費(fèi)。

Output

每個(gè)詢問(wèn)輸出一行，如果不可達(dá)或稅費(fèi)小于 3 則輸出 ‘?’。

Sample 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

Sample Output

Case 1: 3 4 Case 2: ? ?

思路做法：

因?yàn)槎愘M(fèi)可能為負(fù)數(shù)，且圖中可能出現(xiàn)負(fù)環(huán)，因此用SPFA更容易檢測(cè)出來(lái)，圖創(chuàng)建好后，從結(jié)點(diǎn)1開(kāi)始運(yùn)行SPFA，若遇到負(fù)環(huán)，需要把負(fù)環(huán)上的點(diǎn)能到達(dá)的點(diǎn)也全部標(biāo)記，表示稅費(fèi)為負(fù)，另外，用初始化的dis（初始為一個(gè)很大的值）來(lái)判斷某點(diǎn)是否可達(dá)，最后根據(jù)稅費(fèi)為負(fù)的標(biāo)記、是否可達(dá)和稅費(fèi)是否超過(guò)3輸出答案。

總結(jié):

SPFA不限制邊必須為正，可以用于判斷負(fù)環(huán)。

代碼:

#include <stdio.h> #include <queue> #include <vector> #include <cmath> using namespace std; #define INF 0x3f3f3f3fconst int N = 200+5; struct Edge{int u, v, w;Edge(){}Edge(int _u, int _v, int _w):u(_u), v(_v), w(_w){} }; vector<Edge> E[N]; int a[N], dis[N], cnt[N], pre[N]; bool inq[N], isNeg[N]; queue<int> q, neg;void addEdge(int u, int v, int w){E[u].push_back(Edge(u, v, w)); //有向 }void negRing(int s){if(isNeg[s]) return;isNeg[s] = 1; neg.push(s);while(!neg.empty()){int u = neg.front(); neg.pop();for(int i = 0, len = E[u].size(); i < len; ++i){Edge e = E[u][i]; int v = e.v;if(isNeg[v]) continue;isNeg[v] = 1; neg.push(v);}} }void SPFA(int s, int n){for(int i = 1; i <= n; ++i){dis[i] = INF; inq[i] = 0; pre[i] = 0;cnt[i] = 0; isNeg[i] = 0;}dis[s] = 0; inq[s] = 1; q.push(s);while(!q.empty()){int u = q.front(); q.pop(); inq[u] = 0;for(int i = 0, len = E[u].size(); i < len; ++i){Edge e = E[u][i]; int v = e.v;if(dis[v] > dis[u] + e.w){cnt[v] = cnt[u] + 1;if(cnt[v] >= n){negRing(v); continue; //打上標(biāo)記}dis[v] = dis[u] + e.w;pre[v] = u;if(!inq[v]){q.push(v); inq[v] = 1;}}}} }int main(){int t; scanf("%d", &t);for(int k = 1; k <= t; ++k){for(int i = 0; i < N; ++i)while(!E[i].empty()) E[i].pop_back();int n; scanf("%d", &n);for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);int m; scanf("%d", &m);for(int i = 0; i < m; ++i){int A, B; scanf("%d %d", &A, &B);addEdge(A, B, pow(a[B]-a[A], 3));}SPFA(1, n);int q; scanf("%d", &q);printf("Case %d:\n", k);for(int i = 1; i <= q; ++i){int p; scanf("%d", &p);if(isNeg[p] || !isNeg[p]&&dis[p]<3 || !pre[p]) printf("?\n");else printf("%d\n", dis[p]);}}return 0; }

總結(jié)

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

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