【題目鏈接】

ybt 1985：【19CSPJ普及組】加工零件
洛谷 P5663 [CSP-J2019] 加工零件

【題目考點】

圖論

SPFA算法

【解題思路】

1. 問題分析

每個工人是一個頂點，傳送帶是邊，構成一個圖。軒軒是1號工人，即為1號頂點。被派工單的工人記為頂點a。

引理1：頂點v接到生產L階段零件的任務。在頂點v的度不為0的前提下，如果L是偶數，那么頂點v需要提供原材料。

• 證明：記頂點v的某一鄰接點為u，v要生產L階段的零件，那么u就要生產第L-1階段的零件。u生產L-1階段的零件又要求v生產L-2階段的零件。依此類推，如果L是個偶數，u最終需要生產第1階段的零件，v最終需要生產第0階段的零件，即提供原材料。

引理2：頂點v接到生產L階段的零件的任務，假設頂點v到1號頂點存在一條長度為n的路徑，如果L >= n，且L - n是偶數，那么1號頂點需要為該任務提供原材料。

• 證明：在這一路徑上，與v相鄰的頂點v1需要生產L-1階段的零件，路徑上與v1相鄰的頂點需要生產L-2階段的零件，一直傳導到1號頂點，1號頂點需要生產L-n階段的零件。根據引理1，如果L-n是偶數，那么1號頂點需要為該任務提供原材料。

定義1：頂點u到頂點v的奇數最短路徑

頂點u到頂點v的長度為奇數的路徑中，最短的路徑。

定義2：頂點u到頂點v的偶數最短路徑

頂點u到頂點v的長度為偶數的路徑中，最短的路徑。

2. 解題算法：

1. 求圖上每一頂點到1號頂點的奇數最短路徑的長度lodd與偶數最短路徑的長度leven。

實現算法：SPFA算法

每個頂點v關聯兩個值：奇數最短路徑長度v.lodd，偶數最短路徑長度v.leven，初始值為無窮大。

1號頂點入隊，1號頂點的偶數最短路徑長度leven設為0。

v相鄰的點u的奇數最短路徑長度，應該是min(v的偶數最短路徑長度加1，u的奇數最短路徑長度)。
v相鄰的點u的偶數最短路徑長度，應該是min(v的奇數最短路徑長度加1，u的偶數最短路徑長度)。
某頂點v出隊后，遍歷其所有相鄰的頂點，設某相鄰點為u，則如果u.lodd > v.leven + 1 或 u.leven > v.lodd + 1，那么改變u的對應的最短路徑長度，并將u入隊。如果不滿足這兩個條件，則不入隊。

循環運行直到隊空。此時與1號頂點連通的頂點的奇數最短路徑和偶數最短路徑就都設置完成了。

2. 查詢結果

輸入數據，v號頂點需要制造L階段零件。

如果L是奇數，判斷L >= v.lodd，如果為真，那么說明1號頂點需要生產L - v.lodd階段的零件，L - v.lodd是偶數，因此1號頂點需要提供原材料。如果為假，則不需要提供原材料。

如果L是偶數，判斷L >= v.leven，如果為真，那么說明1號頂點需要生產L - v.leven階段的零件，L - v.leven是偶數，因此1號頂點需要提供原材料。如果為假，則不需要提供原材料。

【題解代碼】

解法1：使用鄰接表 （vector邊表）

#include<bits/stdc++.h> using namespace std; #define N 100005 #define MAXINT 0x3f3f3f3f //表示無窮大，大于L的最大值10^9 //鄰接表 int lodd[N], leven[N]; vector<int> edge[N];//邊表 bool vis[N]; //求每一點到1號頂點的奇數最短路徑長度和偶數最短路徑長度 void initPathLength() {memset(lodd, 0x3f, sizeof(lodd));memset(leven, 0x3f, sizeof(leven));int u, v;leven[1] = 0;//自己到自己的最短偶數路徑長度為0queue<int> que;//隊列保存頂點編號que.push(1);vis[1] = true;while(que.empty() == false){u = que.front();//出隊的頂點u que.pop();vis[u] = false;for(int i = 0; i < edge[u].size(); ++i)//遍歷u的鄰接頂點 {v = edge[u][i];//v是u的鄰接頂點if(lodd[v] > leven[u] + 1 || leven[v] > lodd[u] + 1){if(lodd[v] > leven[u] + 1)lodd[v] = leven[u] + 1;if(leven[v] > lodd[u] + 1)leven[v] = lodd[u] + 1;if(vis[v] == false){vis[v] = true;que.push(v);}}}} }int main() {int n, m, q, u, v, a, l;scanf("%d %d %d", &n, &m, &q);for(int i = 0; i < m; ++i){scanf("%d %d", &u, &v);//無向圖添加邊 edge[u].push_back(v);edge[v].push_back(u);}initPathLength();for(int i = 0; i < q; ++i){scanf("%d %d", &a, &l);if(l % 2 == 1 && l >= lodd[a] //如果l是奇數且大于等于a的奇數最短路徑 || l % 2 == 0 && l >= leven[a]) //或如果l是偶數且大于等于a的偶數最短路徑 printf("Yes\n");elseprintf("No\n");}return 0; }

解法2：使用鄰接表 （靜態邊鏈表）

#include<bits/stdc++.h> using namespace std; #define N 100005 #define MAXINT 1000000005 //表示無窮大，大于L的最大值10^9 //鄰接表 typedef struct Ver//頂點 {int next;//下一個邊結點的地址int lodd, leven;//奇數最短路徑長度，偶數最短路徑長度Ver(){next = 0;lodd = leven = MAXINT;//初始值為無窮大} }Ver; typedef struct Edg//邊 {int verNum;//頂點編號int next;//下一個邊結點的地址 }Edg; Ver ver[N];//頂點數組 Edg edg[2*N];//邊結點的結點池。邊最多有10^5個，構造鄰接表，每個邊生成兩個邊結點，所以數組要開2N int ep = 1;//edg數組待分配地址 //添加邊，在邊鏈表上用頭插法 void addEdge(int u, int v) {int lh, edgP;//lh:邊鏈表的頭 edgP:新的邊結點lh = ver[u].next;//在結點u后面的邊鏈表中添加邊結點vedgP = ep++;//分配新的邊結點edg[edgP].verNum = v;ver[u].next = edgP;edg[edgP].next = lh;lh = ver[v].next;//在結點v后面的邊鏈表中添加邊結點uedgP = ep++;//分配新的邊結點edg[edgP].verNum = u;ver[v].next = edgP;edg[edgP].next = lh; } //求每一點到1號頂點的奇數最短路徑長度和偶數最短路徑長度 void initPathLength() {int u, v;ver[1].leven = 0;//自己到自己的最短偶數路徑長度為0queue<int> que;//隊列保存頂點編號que.push(1);while(que.empty() == false){v = que.front();//出隊的頂點v的地址que.pop();for(int p = ver[v].next; p != 0; p = edg[p].next)//遍歷邊鏈表，即遍歷v周圍的頂點u{u = edg[p].verNum;//u是v的鄰接點的地址if(ver[u].lodd > ver[v].leven + 1 || ver[u].leven > ver[v].lodd + 1){if(ver[u].lodd > ver[v].leven + 1)ver[u].lodd = ver[v].leven + 1;if(ver[u].leven > ver[v].lodd + 1)ver[u].leven = ver[v].lodd + 1;que.push(u);}}} }int main() {int n, m, q, u, v, a, l;scanf("%d %d %d", &n, &m, &q);for(int i = 0; i < m; ++i){scanf("%d %d", &u, &v);addEdge(u, v);}initPathLength();for(int i = 0; i < q; ++i){scanf("%d %d", &a, &l);if(l % 2 == 0)//如果l是偶數{if(l >= ver[a].leven)printf("Yes\n");elseprintf("No\n");}else//如果l是奇數{if(l >= ver[a].lodd)printf("Yes\n");elseprintf("No\n");}}return 0; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1985：【19CSPJ普及组】加工零件 | 洛谷 P5663 [CSP-J2019] 加工零件的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。