1003 Emergency (25 分)

• 題意 ：求無(wú)向圖中最短路的數(shù)量，以及在最短路情況下，點(diǎn)權(quán)之和最大是多少
• 思路 ：dijkstra的擴(kuò)展一般在第三步“用t更新其它點(diǎn)“；spfa不能用來(lái)求最短路的數(shù)量（因?yàn)槊總€(gè)點(diǎn)可能被更新多次）；假設(shè)有三個(gè)點(diǎn)可以走到終點(diǎn)x，那么從起點(diǎn)s走到x的路徑分為三類，s->1->x…，如果d1<d2<d3，最短距離的數(shù)量就是走到第一個(gè)點(diǎn)的數(shù)量，如果d1=d2<d3，前兩個(gè)相加，同理，求最短路情況下點(diǎn)權(quán)和最大，就是三者取max（如果三者相同）；cnt數(shù)組記錄從起點(diǎn)走到i的最短路徑數(shù)量；sum數(shù)組記錄從起點(diǎn)到i的最大點(diǎn)權(quán)
• 語(yǔ)法 ：如果點(diǎn)數(shù)<=1000，鄰接矩陣就沒(méi)有問(wèn)題，>=1e4就一定要鄰接表存；

#include <iostream> #include <cstring>using namespace std;const int N = 510;int n, m, S, T; int w[N], g[N][N]; int cnt[N], sum[N]; int dist[N]; bool st[N];void dijkstra() {memset(dist, 0x3f, sizeof dist); // 初始化dist[S] = 0, cnt[S] = 1, sum[S] = w[S];for (int i = 0; i < n - 1; i ++ ){int t = -1;for (int j = 0; j < n; j ++ )if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;st[t] = true; // 標(biāo)記for (int j = 0; j < n; j ++ )if (dist[j] > dist[t] + g[t][j]){dist[j] = dist[t] + g[t][j];cnt[j] = cnt[t];sum[j] = sum[t] + w[j];}else if (dist[j] == dist[t] + g[t][j]){cnt[j] += cnt[t];sum[j] = max(sum[j], sum[t] + w[j]);}} }int main() {cin >> n >> m >> S >> T;for (int i = 0; i < n; i ++ ) cin >> w[i];memset(g, 0x3f, sizeof g); // 初始化while (m -- ){int a, b, c;cin >> a >> b >> c;g[a][b] = g[b][a] = min(g[a][b], c); // 無(wú)向圖}dijkstra();cout << cnt[T] << ' ' << sum[T];return 0; }

• 思路 ：dijkstra中在循環(huán)for或者while的外面初始化時(shí)，起點(diǎn)的st不要設(shè)成true！堆優(yōu)化版在一個(gè)點(diǎn)被更新松弛后將它放入優(yōu)先隊(duì)列內(nèi)
• 語(yǔ)法 ：堆優(yōu)化版寫(xiě)成鏈?zhǔn)角跋蛐?#xff0c;M開(kāi)成N*N

// 堆優(yōu)化版 #include <iostream> #include <cstring> #include <queue>using namespace std;const int N = 510, M = N * N; // 注意M大小typedef pair<int, int> pii;int h[N], w[M], e[M], ne[M], idx; int wt[N]; int dist[N]; bool st[N]; int cnt[N], sum[N]; int n, m, S, T;void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; }void dijkstra() {memset(dist, 0x3f, sizeof dist);dist[S] = 0;cnt[S] = 1, sum[S] = wt[S];priority_queue<pii, vector<pii>, greater<pii>> heap;heap.push({0, S});// st[S] = true; 注意！！！while (heap.size()){auto t = heap.top();heap.pop();int ver = t.second, distance = t.first;if (st[ver]) continue;st[ver] = true;for (int i = h[ver]; i != -1; i = ne[i]){int j = e[i];if (dist[j] > dist[ver] + w[i]){dist[j] = dist[ver] + w[i];cnt[j] = cnt[ver];sum[j] = sum[ver] + wt[j];heap.push({dist[j], j}); // 被更新松弛了的點(diǎn)要放入優(yōu)先隊(duì)列內(nèi)}else if (dist[j] == dist[ver] + w[i]){cnt[j] += cnt[ver];sum[j] = max(sum[j], sum[ver] + wt[j]);}}} }int main() {memset(h, -1, sizeof h);cin >> n >> m >> S >> T;for (int i = 0; i < n; i ++ ) cin >> wt[i];while (m -- ){int a, b, c;cin >> a >> b >> c;add(a, b, c);add(b, a, c);}dijkstra();cout << cnt[T] << ' ' << sum[T];return 0; }

1018 Public Bike Management (30 分)

題意 ：

• 給一個(gè)終點(diǎn)，要從起點(diǎn)出發(fā)，要找到一條路徑，第一優(yōu)先級(jí)的要求是 距離最短；如果有很多條距離相同的路徑，第二優(yōu)先級(jí)，最初帶去的自行車數(shù)量越少越好；第三優(yōu)先級(jí)，最終帶回的自行車數(shù)量越少越好

思路 ：

• 多關(guān)鍵字的dijk，但前面的問(wèn)題是可以在dijk過(guò)程中去滿足，這題比較特殊，后面兩個(gè)要求是不能再dijk過(guò)程中去滿足的；比如從兩個(gè)點(diǎn)中選一個(gè)去第三個(gè)點(diǎn)，第一個(gè)點(diǎn)出發(fā)要帶5輛車，第二個(gè)點(diǎn)出發(fā)要帶6輛車，但我們無(wú)法分析到底哪個(gè)點(diǎn)更好，比如到第三個(gè)點(diǎn)恰好缺5輛，第一個(gè)點(diǎn)就更好，但也有可能缺6輛，第二個(gè)點(diǎn)就更好。像以前的關(guān)鍵字都是累加的，第一關(guān)鍵字距離第二關(guān)鍵字時(shí)間，時(shí)間肯定越短越好，但這題無(wú)法判斷
• 所以這題就比較復(fù)雜，先做一遍dijk，求每個(gè)點(diǎn)到終點(diǎn)的最短距離，然后再去把所有從起點(diǎn)到終點(diǎn)的最短距離搜索一遍，從所有的最短路徑中找后兩個(gè)條件最好的
• 這題本應(yīng)是指數(shù)級(jí)復(fù)雜度，但對(duì)于一個(gè)隨機(jī)圖而言，最短路徑不會(huì)太多
• 求dijk是為了剪枝，保證走的時(shí)候是最短路徑；比如我們當(dāng)前在u點(diǎn)，要判斷u點(diǎn)走到v點(diǎn)有沒(méi)有可能使是最短路徑呢？可以用dist數(shù)組判斷，如果dist[u] = dist[u -> v] + dist[v]，那么說(shuō)明我們搜的時(shí)候可以從u走到v，這其實(shí)就是一個(gè)剪枝
• 用一個(gè)變量s表示當(dāng)前需要帶去多少自行車，可以是負(fù)數(shù)，在過(guò)程中，負(fù)數(shù)的最小值就是我們需要帶去的自行車；帶回的自行車是多少呢？就是看最終s的值是多少，再加上帶去的數(shù)量
• 爆搜時(shí)用一個(gè)vector容器 的 path來(lái)存路徑，ans來(lái)存答案路徑
• 當(dāng)爆搜到終點(diǎn)時(shí)，在計(jì)算需要帶的數(shù)量sd時(shí)，此時(shí)的mins有可能為正數(shù)，也就是一輛都不用帶，所以要和0取最小的，最終需要帶走的數(shù)量bg就是s加上sd
• 注意這個(gè)mins不是全局變量！！是當(dāng)前這條路徑上的最小值
• dfs時(shí)，假設(shè)放了，之后還要回溯pop_back

語(yǔ)法 ：

• s -= (C + 1) / 2 - c[u];是上取整
• 帶權(quán)無(wú)向圖，首先初始化g數(shù)組為無(wú)窮；帶權(quán)，未說(shuō)明是否有重邊，因此取min
• 初始時(shí)，dfs前，不要忘了往里面加上起點(diǎn)0

#include <iostream> #include <vector> #include <cstring> using namespace std;#define pb push_backconst int N = 510, INF = 0x3f3f3f3f;int C, n, S, m; int c[N]; int g[N][N]; int dist[N]; bool st[N];vector<int> path, ans;int send = INF, bring = INF;void dijkstra() {memset(dist, 0x3f, sizeof dist);dist[S] = 0;for (int i = 0; i < n; i ++ ){int t = -1;for (int j = 0; j <= n; j ++ )if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;st[t] = true;for (int j = 0; j <= n; j ++ )dist[j] = min(dist[j], dist[t] + g[t][j]);} }void dfs(int u, int s, int mins) {if (u){s -= (C + 1) / 2 - c[u];mins = min(mins, s);}if (u == S){int sd = abs(min(0, mins));int bg = sd + s;if (sd < send || (sd == send && bring > bg))ans = path, send = sd, bring = bg;return ;}for (int i = 1; i <= n; i ++ )if (dist[u] == dist[i] + g[u][i]){path.pb(i);dfs(i, s, mins);path.pop_back();} }int main() {scanf("%d%d%d%d", &C, &n, &S, &m);for (int i = 1; i <= n && scanf("%d", &c[i]); i ++ );memset(g, 0x3f, sizeof g);for (int i = 0, x, y, z; i < m && scanf("%d%d%d", &x, &y, &z); i ++ )g[x][y] = g[y][x] = min(g[x][y], z);dijkstra();path.pb(0);dfs(0, 0, 0);printf("%d 0", send);for (int i = 1; i < ans.size(); i ++ ) printf("->%d", ans[i]);printf(" %d", bring); }

1122 Hamiltonian Cycle (25 分)

題意 ：

• Hamiltonian Cycle哈密頓回路
• 哈密頓回路問(wèn)題是找到一個(gè)包含圖中每個(gè)頂點(diǎn)的簡(jiǎn)單回路。
• 在本題中，你需要做的是判斷給定路徑是否為哈密頓回路。
• 無(wú)向圖

思路 ：

• 恰好每個(gè)點(diǎn)走一次，且第一個(gè)點(diǎn)和最后一個(gè)點(diǎn)是同一個(gè)點(diǎn)
• 如果滿足了以上兩個(gè)要求，就按它給的路徑走一遍，如果從當(dāng)前這個(gè)點(diǎn)都能走到下一個(gè)點(diǎn)，且所有點(diǎn)都走了一次，就是哈密頓路徑
• 這題有一個(gè)很坑的地方，題目只說(shuō)了圖中點(diǎn)的數(shù)量是200，但沒(méi)說(shuō)輸入的路徑的點(diǎn)數(shù)也是200，所以如果路徑數(shù)組開(kāi)太小，會(huì)有一個(gè)點(diǎn)過(guò)不了

#include <iostream> using namespace std;const int N = 210;int n, m; int nodes[N * 2], cnt; bool g[N][N]; bool st[N];bool check() {if (cnt != n + 1 || nodes[0] != nodes[cnt - 1]) return false;for (int i = 1; i <= n; i ++ ) st[i] = 0;for (int i = 0; i < cnt - 1; i ++ ){st[nodes[i]] = true;if (!g[nodes[i]][nodes[i + 1]])return false;}for (int i = 1; i <= n; i ++ )if (!st[i])return false;return true; }int main() {scanf("%d%d", &n, &m);int a, b;while (m -- ){scanf("%d%d", &a, &b);g[a][b] = g[b][a] = true;}int k; scanf("%d", &k);while (k -- ){scanf("%d", &cnt);for (int i = 0; i < cnt; i ++ ) scanf("%d", &nodes[i]);if (check()) puts("YES");else puts("NO");} }

1126 Eulerian Path (25 分)

題意 ：

• Eulerian Path歐拉路徑
• circuit環(huán)路；degree度數(shù)
• 歐拉路徑是圖中的一條路徑，該路徑滿足恰好訪問(wèn)每個(gè)邊一次。
• 歐拉回路是一條在同一頂點(diǎn)處開(kāi)始和結(jié)束的歐拉路徑。
• 如果一個(gè)連通圖的所有頂點(diǎn)的度數(shù)都為偶數(shù)，那么這個(gè)連通圖具有歐拉回路，且這個(gè)圖被稱為歐拉圖
• 如果一個(gè)連通圖中有兩個(gè)頂點(diǎn)的度數(shù)為奇數(shù)，其他頂點(diǎn)的度數(shù)為偶數(shù)，那么所有歐拉路徑都從其中一個(gè)度數(shù)為奇數(shù)的頂點(diǎn)開(kāi)始，并在另一個(gè)度數(shù)為奇數(shù)的頂點(diǎn)結(jié)束。
• 具有歐拉路徑但不具有歐拉回路的圖被稱為半歐拉圖。
• 現(xiàn)在，給定一個(gè)無(wú)向圖，請(qǐng)你判斷它是歐拉圖、半歐拉圖還是非歐拉圖。
  

思路 ：

• 每個(gè)點(diǎn)的度數(shù)是什么呢？就是這個(gè)點(diǎn)連的邊數(shù)
• 首先不管是歐拉圖還是半歐拉圖都必須是連通的；所以第一步是判斷連通性，從某個(gè)點(diǎn)出發(fā)，看能否把所有點(diǎn)搜到，dfs或者bfs；這個(gè)判斷連通性是 圖的遍歷，時(shí)間復(fù)雜度為 點(diǎn)數(shù)加邊數(shù)
• 然后判斷度數(shù)，直接按照定義即可
• 判斷連通性的寫(xiě)法 ：從1號(hào)點(diǎn)出發(fā)，看能搜到幾個(gè)點(diǎn)，遍歷的時(shí)候?yàn)榱吮苊庵貜?fù)搜索，要有一個(gè)判重?cái)?shù)組

#include <iostream> using namespace std;const int N = 510;int n, m; bool g[N][N]; int d[N]; bool st[N]; // dfs用int dfs(int u) {st[u] = true;int cnt = 1;for (int i = 1; i <= n; i ++ ){if (!st[i] && g[u][i])cnt += dfs(i);}return cnt; }int main() {scanf("%d%d", &n, &m);int a, b;while (m -- ){scanf("%d%d", &a, &b);g[a][b] = g[b][a] = true;d[a] ++ , d[b] ++ ;}int cnt = dfs(1);printf("%d", d[1]);for (int i = 2; i <= n; i ++ ) printf(" %d", d[i]);puts("");if (cnt == n){int s = 0;for (int i = 1; i <= n; i ++ )if (d[i] % 2)s ++ ;if (!s) puts("Eulerian");else if (s == 2) puts("Semi-Eulerian");else puts("Non-Eulerian");}elseputs("Non-Eulerian"); }

1134 Vertex Cover (25 分)

題意 ：

• 如果圖中的一個(gè)頂點(diǎn)集合能夠滿足圖中的每一條邊都至少有一個(gè)端點(diǎn)在該集合內(nèi)，那么這個(gè)頂點(diǎn)集合就是圖的頂點(diǎn)覆蓋。
• 現(xiàn)在給定一張圖，以及若干個(gè)頂點(diǎn)集合，請(qǐng)你判斷這些頂點(diǎn)集合是否是圖的頂點(diǎn)覆蓋。

思路 ：

• 直接模擬即可

#include <iostream> #include <cstring>using namespace std;const int N = 10010;int n, m; struct Edge {int a, b; }e[N]; bool st[N];int main() {cin >> n >> m;for (int i = 0; i < m; i ++ ) cin >> e[i].a >> e[i].b;int k;cin >> k;while (k -- ){int cnt;cin >> cnt;memset(st, 0, sizeof st);while (cnt -- ){int x;cin >> x;st[x] = true;}int i;for (i = 0; i < m; i ++ )if (!st[e[i].a] && !st[e[i].b])break;if (i == m) puts("Yes");else puts("No");}return 0; }

1142 Maximal Clique (25 分)

題意 ：

• 在一個(gè)無(wú)向圖中，如果一個(gè)頂點(diǎn)子集滿足子集內(nèi)的任意兩個(gè)不同頂點(diǎn)之間都是相連的，那么這個(gè)頂點(diǎn)子集就被稱為一個(gè)團(tuán)。
• 如果一個(gè)團(tuán)不能通過(guò)加入某個(gè)新的頂點(diǎn)來(lái)擴(kuò)展成一個(gè)更大的團(tuán)，那么該團(tuán)就被稱為最大團(tuán)。
• 現(xiàn)在，你需要判斷給定頂點(diǎn)子集能否構(gòu)成一個(gè)最大團(tuán)。

#include <iostream> #include <cstring> using namespace std;const int N = 210;int n, m; bool g[N][N]; int nodes[N], cnt; bool st[N];bool check_clique() {for (int i = 0; i < cnt; i ++ )for (int j = 0; j < i; j ++ )if (!g[nodes[i]][nodes[j]])return false;return true; }bool check_maximum() {memset(st, 0, sizeof st);for (int i = 0; i < cnt; i ++ )st[nodes[i]] = true;for (int i = 1; i <= n; i ++ ){if (!st[i]){bool success = false;for (int j = 0; j < cnt; j ++ )if (!g[i][nodes[j]]){success = true;break;}if (!success) return false;}}return true; }int main() {scanf("%d%d", &n, &m);int a, b;while (m -- ){scanf("%d%d", &a, &b);g[a][b] = g[b][a] = true;}int k; scanf("%d", &k);while (k -- ){scanf("%d", &cnt);for (int i = 0; i < cnt; i ++ ) scanf("%d", &nodes[i]);if (check_clique()){if (check_maximum()) puts("Yes");else puts("Not Maximal");}elseputs("Not a Clique");} }

1146 Topological Order (25 分)

題意 ：

• 以下哪個(gè)選項(xiàng)不是從給定的有向圖中獲得的拓?fù)湫蛄?#xff1f;
• 現(xiàn)在，請(qǐng)你編寫(xiě)一個(gè)程序來(lái)測(cè)試每個(gè)選項(xiàng)。

思路 ：

• 將輸入的每一條邊存下來(lái)
• 對(duì)于每對(duì)詢問(wèn)，遍歷每條邊，如果邊的起點(diǎn)比邊的終點(diǎn)在詢問(wèn)中出現(xiàn)的位置晚，說(shuō)明詢問(wèn)不合格

語(yǔ)法 ：

• is_first的使用，如果是true，將其轉(zhuǎn)為false；否則輸出空格

#include <iostream> #include <cstring>using namespace std;const int N = 1010, M = 10010;int n, m; struct Edge {int a, b; }e[M]; int p[N];int main() {cin >> n >> m;for (int i = 0; i < m; i ++ ) cin >> e[i].a >> e[i].b;int k;cin >> k;bool is_first = true;for (int i = 0; i < k; i ++ ){for (int j = 1; j <= n; j ++ ){int x;cin >> x;p[x] = j;}bool success = true;for (int j = 0; j < m; j ++ )if (p[e[j].a] > p[e[j].b]){success = false;break;}if (!success){if (is_first) is_first = false;else cout << ' ';cout << i;}}cout << endl;return 0; }

1150 Travelling Salesman Problem (25 分)

思路 ：

• 如果所給的路徑中不連通，success為false，sum為-1，輸出NA；如果第一個(gè)點(diǎn)和最后一個(gè)不是同一個(gè)點(diǎn)，沒(méi)有遍歷所有點(diǎn)；遍歷完路徑后，如果有點(diǎn)沒(méi)有被路徑包含，則success為false，輸出不是一個(gè)訪問(wèn)了所有城市的回路；
• 如果路徑點(diǎn)的數(shù)量等于n+1，說(shuō)明是簡(jiǎn)單回路，否則就不是簡(jiǎn)單回路
• 然后動(dòng)態(tài)維護(hù)最小距離和最小距離的組號(hào)
• 無(wú)向帶權(quán)圖，因此初始化距離為正無(wú)窮
• 用sum表示路徑和，如果是-1，說(shuō)明無(wú)法計(jì)算；success表示是否是否訪問(wèn)了所有城市

#include <iostream> #include <cstring>using namespace std;const int N = 210, INF = 0x3f3f3f3f;int n, m; int d[N][N], vers[310]; bool st[N];int main() {cin >> n >> m;memset(d, 0x3f, sizeof d);for (int i = 0; i < m; i ++ ){int a, b, c;cin >> a >> b >> c;d[a][b] = d[b][a] = c;}int k;cin >> k;int min_dist = INF, min_id;for (int T = 1; T <= k; T ++ ){int cnt;cin >> cnt;for (int i = 0; i < cnt; i ++ ) cin >> vers[i];int sum = 0;bool success = true;memset(st, 0, sizeof st);for (int i = 0; i + 1 < cnt; i ++ ){int a = vers[i], b = vers[i + 1];if (d[a][b] == INF){sum = -1;success = false;break;}else sum += d[a][b];st[a] = true;}for (int i = 1; i <= n; i ++ )if (!st[i]){success = false;break;}if (vers[0] != vers[cnt - 1]) success = false;if (sum == -1) printf("Path %d: NA (Not a TS cycle)\n", T);else{if (!success) printf("Path %d: %d (Not a TS cycle)\n", T, sum);else{if (cnt == n + 1) printf("Path %d: %d (TS simple cycle)\n", T, sum);else printf("Path %d: %d (TS cycle)\n", T, sum);if (min_dist > sum){min_dist = sum;min_id = T;}}}}printf("Shortest Dist(%d) = %d\n", min_id, min_dist);return 0; }

1154 Vertex Coloring (25 分)

題意 ：

• 一個(gè)合適的頂點(diǎn)著色是指用各種顏色標(biāo)記圖中各個(gè)頂點(diǎn)，使得每條邊的兩個(gè)端點(diǎn)的顏色都不相同。
• 如果一種合適的頂點(diǎn)著色方案使用了一共 k 種不同的顏色，則稱其為合適的 k 著色（k-coloring)。
• 現(xiàn)在，你需要判斷給定的著色方案是否是合適的 k 著色方案。

思路 ：

• 用結(jié)構(gòu)體存邊
• 對(duì)于每一個(gè)詢問(wèn)，首先遍歷所有邊，如果所有邊的顏色都沒(méi)有出現(xiàn)矛盾，再判斷顏色數(shù)量是否是k種

#include <iostream> #include <cstring> #include <unordered_set>using namespace std;const int N = 10010;int n, m; struct Edge {int a, b; }e[N]; int color[N];int main() {cin >> n >> m;for (int i = 0; i < m; i ++ ) cin >> e[i].a >> e[i].b;int k;cin >> k;while (k -- ){for (int i = 0; i < n; i ++ ) cin >> color[i];bool success = true;for (int i = 0; i < m; i ++ )if (color[e[i].a] == color[e[i].b]){success = false;break;}if (success){unordered_set<int> S;for (int i = 0; i < n; i ++ ) S.insert(color[i]);printf("%d-coloring\n", S.size());}else puts("No");}return 0; } 與50位技術(shù)專家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的PAT甲级题目翻译+答案 AcWing（图论）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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