最短路徑
A1018. Public Bike Management
思路：
- 首先，為了編寫代碼，并得知所有結(jié)點(diǎn)中，哪個(gè)結(jié)點(diǎn)的點(diǎn)權(quán)(自行車數(shù)目)不夠或者冗余，我們采取的方案是：把每個(gè)點(diǎn)的點(diǎn)權(quán)都減去Cmax/2，從而可以用點(diǎn)權(quán)的正負(fù)來(lái)直接判斷當(dāng)前車站是需要補(bǔ)給還是需要帶走額外的車輛。
- 因?yàn)槌艘敵?strong>最短路徑以外，還要輸出從PBMC攜帶出來(lái)的自行車數(shù)目和從問(wèn)題車站Sp帶回的自行車數(shù)目。
因此，我們采取的方案是：對(duì)每個(gè)頂點(diǎn)增加兩個(gè)屬性：
(1)從PBMC到當(dāng)前車站必須攜帶的自行車數(shù)目Need;
(2)到達(dá)當(dāng)前車站時(shí)手上多余的自行車數(shù)目Remain。
也就是說(shuō)，
如果當(dāng)前車站u的點(diǎn)權(quán)weight[u]為正，說(shuō)明需要從該車站額外帶走自行車，所以，新的Remain等于舊的Remain加上weight[u]。
如果當(dāng)前車站u的點(diǎn)權(quán)weight[u]為負(fù)，說(shuō)明當(dāng)前車站需要補(bǔ)給的自行車數(shù)量為abs(weight[u])。此時(shí)，如果Remain大于0，就拿Remain來(lái)補(bǔ)給，但如果Remain補(bǔ)給后還是不夠，剩下的只能從PBMC攜帶了，這時(shí)要記得更新Need，讓Need加上這個(gè)不夠的差值。
//--當(dāng)前結(jié)點(diǎn)編號(hào)為id--
int id = tempPath[i];
//--如果點(diǎn)權(quán)大于0，說(shuō)明需要帶走一部分自行車--
if (weight[id] > 0)
{
remain += weight[id];
}
//--如果點(diǎn)權(quán)不超過(guò)0，需要補(bǔ)給--
else
{
//--如果當(dāng)前持有量remain足夠補(bǔ)給--
if (remain > abs(weight[id]))
{
//--那么就用當(dāng)前持有量remain減去需要補(bǔ)給的量--
remain -= abs(weight[id]);
}
//--如果當(dāng)前持有量remain不夠補(bǔ)給--
else
{
//--不夠的部分從PBMC攜帶--
need += abs(weight[id]) - remain;
//--當(dāng)前持有的自行車全部用來(lái)補(bǔ)給，所以歸0--
remain = 0;
}
}
- 這道題需要先使用Dijkstra算法求出所有的最短路徑。再使用DFS算法從這些最短路徑中選出need最小的，如果need相同，則選擇remain最小的。
注意點(diǎn)：
- 大家要注意一點(diǎn)：從起點(diǎn)PBMC出發(fā)到達(dá)問(wèn)題站點(diǎn)Sp的過(guò)程中，就需要調(diào)整路徑上所有站點(diǎn)的狀態(tài)至Perfect。
- 這道題不能單單的使用Dijkstra算法來(lái)搞定，因?yàn)閙inNeed和minRemain在路徑上的傳遞不滿足最優(yōu)子結(jié)構(gòu)，因?yàn)樗皇?strong>簡(jiǎn)單的相加過(guò)程。
事實(shí)上，只有當(dāng)所有路徑都確定后，才能去選擇最小的need和最小的remain。
代碼邏輯：
- 這次定義的新變量中，有3個(gè)vector變量。pre[]前驅(qū)和tempPath, path臨時(shí)路徑和最優(yōu)路徑。
》- 先看main()函數(shù)，首先輸入車站的最大容量Cmax，頂點(diǎn)數(shù)n，問(wèn)題站點(diǎn)Sp，邊數(shù)m。然后使用鄰接矩陣初始化圖G，圖G的初值均為INF。接下來(lái)，在輸入點(diǎn)權(quán)的時(shí)候減去最大容量的一半Cmax/2。最后，更新邊權(quán)G[u][v]，而且要手動(dòng)保證G[v][u] = G[u][v]。
- 這一步開(kāi)始，就直接進(jìn)入到了Dijkstra算法和DFS算法。
這里我們讓起點(diǎn)s作為參數(shù)傳入Dijkstra算法，這里起點(diǎn)的編號(hào)為0。
緊接著，將問(wèn)題站點(diǎn)Sp作為參數(shù)傳入DFS算法。- Dijkstra算法：數(shù)組d[]記錄最短距離。
第一步，初始化d[]，初值均為INF。接下來(lái)，定義前驅(qū)結(jié)點(diǎn)pre[]，遍歷n個(gè)結(jié)點(diǎn)，使pre[i] = i;
第二步，遍歷n個(gè)結(jié)點(diǎn)，找到未訪問(wèn)結(jié)點(diǎn)中d[]最小的。特殊情況：沒(méi)有小于INF的d[u]，說(shuō)明剩下的頂點(diǎn)和起點(diǎn)s不連通。注意：如果頂點(diǎn)u已經(jīng)訪問(wèn)，要記得將u的訪問(wèn)狀態(tài)更新為true。
第三步，重新遍歷n個(gè)頂點(diǎn)。這次，如果頂點(diǎn)v未被訪問(wèn)，而且頂點(diǎn)u和v之間可到達(dá)。我們就看以u(píng)為中介點(diǎn)，能否使最短距離d[v]更小，
可以的話，便更新。注意：更新d[v]的同時(shí)，還要將前驅(qū)結(jié)點(diǎn)數(shù)組pre[]先清空，再把頂點(diǎn)u加到pre[v]中(本來(lái)初始化中，pre[v]=v，現(xiàn)在pre[v]=u，也就是說(shuō)v的前驅(qū)頂點(diǎn)是u)。
不可以的話，那么如果以u(píng)為中介點(diǎn)，最短距離和d[v]相同。那么不清空pre[v]，而是直接將頂點(diǎn)u加入到pre[v]中，也就是，頂點(diǎn)v的前驅(qū)頂點(diǎn)有2個(gè)，一個(gè)是v，后面的是u。
注意：這里需要注意的一點(diǎn)是，昨天做的題可以在更新d[v]的時(shí)候，可以同步更新最大點(diǎn)權(quán)之和w[]和最短路徑條數(shù)num[]，是因?yàn)?strong>w[]和num[]在路徑上的傳遞滿足最優(yōu)子結(jié)構(gòu)。然而這道題，我們只是同步更新了頂點(diǎn)v的前驅(qū)頂點(diǎn)u。沒(méi)有同步更新最少攜帶的數(shù)目minNeed和最少帶回的數(shù)目minRemain。因?yàn)檫@倆不滿足最優(yōu)子結(jié)構(gòu)，求解并不是簡(jiǎn)單的相加過(guò)程。只有在所有路徑確定后，才可以去選擇最小的need和最小的remain。- DFS算法：
我們以問(wèn)題站點(diǎn)Sp作為參數(shù)傳入DFS(int v)中。
如果Sp是起點(diǎn)(0號(hào)頂點(diǎn))(不一定一開(kāi)始就進(jìn)入v=0這個(gè)if{}中，因?yàn)镈FS()在不斷遞歸調(diào)用，遞歸到PBMC起點(diǎn)了)，則向臨時(shí)路徑tempPath中添加該頂點(diǎn)Sp(起點(diǎn))。然后倒著枚舉tempPath中的每個(gè)頂點(diǎn)i?？纯催@個(gè)站點(diǎn)i的點(diǎn)權(quán)是否大于0——
如果點(diǎn)權(quán)大于0，則帶走特定數(shù)量的自行車。
如果點(diǎn)權(quán)不超過(guò)0，說(shuō)明需要補(bǔ)給，如果當(dāng)前持有量夠(可能已經(jīng)經(jīng)過(guò)一個(gè)站點(diǎn)了，從那個(gè)站點(diǎn)中帶出來(lái)了一些)，就拿來(lái)補(bǔ)給。如果不夠，就說(shuō)明需要從PBMC中帶。
當(dāng)枚舉完該tempPath臨時(shí)路徑的所有站點(diǎn)后，我們的remain和need都得到了更新，如果新的remain和need比minNeed和minRemain更優(yōu)，則更新minNeed和minRemain，同時(shí)，將當(dāng)前這個(gè)tempPath臨時(shí)路徑更新為最優(yōu)路徑path。最后，將tempPath中的尾元素(也就是起點(diǎn))刪除掉。返回return。
總結(jié)一下：當(dāng)DFS(s)中的頂點(diǎn)為起點(diǎn)時(shí)，說(shuō)明已經(jīng)倒著遞歸到了最后一步。
假如，當(dāng)前DFS(v)中的結(jié)點(diǎn)v不是起點(diǎn)，那么就將頂點(diǎn)v加入到tempPath中，然后順著枚舉頂點(diǎn)v的每個(gè)前驅(qū)頂點(diǎn)pre[v][i]。最后遞歸結(jié)束，不斷地返回過(guò)程中，不斷地刪除tempPath臨時(shí)路徑的尾元素。(原因是tempPath可能會(huì)不斷地新添頂點(diǎn)，如果不刪除干凈，可能會(huì)計(jì)算錯(cuò)誤)- 輸出答案：當(dāng)Dijkstra算法和DFS算法均進(jìn)行完后，輸出minNeed和minRemain。值得一提的是，在輸出仿真最優(yōu)路徑的時(shí)候，需要倒著枚舉最優(yōu)路徑path的每一個(gè)頂點(diǎn)(原因是DFS()在遞歸的時(shí)候，是從問(wèn)題站點(diǎn)(i.e. 目的地)開(kāi)始，在起點(diǎn)(i.e.PBMC起點(diǎn)))結(jié)束的。
完整代碼：
//--s為起點(diǎn)--
void Dijkstra(int s)
{
fill(d, d + MAXV, INF);
for (int i = 0; i <= n; i++)
{
pre[i].push_back(i);
}
d[s] = 0;
for (int i = 0; i <= n; i++) // 這里寫成(i<n)或(i<=n)結(jié)果沒(méi)有區(qū)別
// 也就是循環(huán)n次和循環(huán)n+1次沒(méi)有區(qū)別
{
int u = -1, MIN = INF;
//--找到未訪問(wèn)的頂點(diǎn)中d[]最小的--
for (int j = 0; j <= n; j++)
{
if (vis[j] == false && d[j] < MIN)
{
u = j;
MIN = d[j];
}
}
//--找不到小于INF的d[u]，說(shuō)明剩下的頂點(diǎn)和起點(diǎn)s不連通--
if (u == -1) return;
//--標(biāo)記u為已訪問(wèn)--
vis[u] = true;
for (int v = 0; v <= n; v++)
{
//--如果v未訪問(wèn)，并且u能到達(dá)v--
if (vis[v] == false && G[u][v] != INF)
{
if (d[u] + G[u][v] < d[v])
{
//--優(yōu)化d[v]--
d[v] = d[u] + G[u][v];
pre[v].clear();
pre[v].push_back(u);
}
else if (d[u] + G[u][v] == d[v])
{
pre[v].push_back(u);
}
}
}
}
}
void DFS(int v)
{
if (v == 0)
{
//--遞歸邊界，葉子結(jié)點(diǎn)--
tempPath.push_back(v);
//--路徑上tempPath上需要攜帶的數(shù)目，需要帶回的數(shù)目--
int need = 0, remain = 0;
//--此處必須倒著枚舉--
for (int i = tempPath.size() - 1; i >= 0; i--)
{
//--當(dāng)前結(jié)點(diǎn)編號(hào)為id--
int id = tempPath[i];
//--如果點(diǎn)權(quán)大于0，說(shuō)明需要帶走一部分自行車--
if (weight[id] > 0)
{
remain += weight[id];
}
//--如果點(diǎn)權(quán)不超過(guò)0，需要補(bǔ)給--
else
{
//--如果當(dāng)前持有量remain足夠補(bǔ)給--
if (remain > abs(weight[id]))
{
//--那么就用當(dāng)前持有量remain減去需要補(bǔ)給的量--
remain -= abs(weight[id]);
}
//--如果當(dāng)前持有量remain不夠補(bǔ)給--
else
{
//--不夠的部分從PBMC攜帶--
need += abs(weight[id]) - remain;
//--當(dāng)前持有的自行車全部用來(lái)補(bǔ)給，所以歸0--
remain = 0;
}
}
}
//--如果需要從PBMC攜帶的自行車數(shù)目可以更少--
if (need < minNeed)
{
//--那么就優(yōu)化minNeed--
minNeed = need;
//--同時(shí)覆蓋minRemain--
minRemain = remain;
//--還要覆蓋最優(yōu)路徑path--
path = tempPath;
}
//--如果攜帶數(shù)目相同，帶回?cái)?shù)目變少--
else if (need == minNeed && remain < minRemain)
{
//--那么就優(yōu)化minRemain--
minRemain = remain;
//--還要覆蓋最優(yōu)路勁path--
path = tempPath;
}
tempPath.pop_back(); // 為什么要?jiǎng)h除尾元素？
return;
}
tempPath.push_back(v);
for (int i = 0; i < pre[v].size(); i++)
{
DFS(pre[v][i]);
}
tempPath.pop_back(); // 這里也要?jiǎng)h除尾元素？
}
int main()
{
scanf("%d%d%d%d", &Cmax, &n, &Sp, &m);
int u, v;
fill(G[0], G[0] + MAXV * MAXV, INF);
for (int i = 1; i <= n; i++)
{
scanf("%d", &weight[i]);
//--點(diǎn)權(quán)減去容量的一半--
weight[i] -= Cmax / 2;
}
for (int i = 0; i < m; i++)
{
scanf("%d%d", &u, &v);
scanf("%d", &G[u][v]);
G[v][u] = G[u][v];
}
Dijkstra(0);
DFS(Sp);
//---輸出需要從PBMC攜帶的最少bike數(shù)目---
printf("%d ", minNeed);
//---輸出仿真最優(yōu)路徑---
for (int i = path.size() - 1; i >= 0; i--)
{
printf("%d", path[i]);
if (i > 0) printf("->");
}
//---輸出需要從問(wèn)題站Sp帶回的最少bike數(shù)目---
printf(" %d", minRemain);
return 0;
}
A1072. Gas Station
思路：
- 首先解決的是頂點(diǎn)的編號(hào)問(wèn)題。我們通過(guò)寫一個(gè)getID()函數(shù)來(lái)搞定。
- 枚舉每個(gè)加油站，使用Dijkstra算法來(lái)得到所有居民房距離該加油站的最短距離。因?yàn)楸绢}中所有的無(wú)向邊都是真實(shí)存在的，所以Dijkstra算法中，頂點(diǎn)編號(hào)的范圍應(yīng)該是1~(n+m)。
- 在我們通過(guò)Dijkstra算法得到某個(gè)加油站的數(shù)組d[maxv]后，還需要獲取其中的最小元素(也就是加油站與居民房的所有最短距離中的最近距離)。也許大家會(huì)有疑惑，我們通過(guò)D算法求得的，是所有居民房距離該加油站的最短距離。還要求所有居民房與加油站的平均距離。
注意點(diǎn)：
- D算法要重復(fù)多次，所以要在開(kāi)頭，也就是每次執(zhí)行算法前都要重置vis數(shù)組為false, d[]數(shù)組為INF。
- 因?yàn)槲覀儠?huì)定義一個(gè)變量最大的最近距離，因?yàn)槭?strong>求最大，所以其初值必須設(shè)為一個(gè)較小的數(shù)(比如-1)。
(怎么理解這個(gè)最大的最近距離呢？先考慮加油站G1，找到離G1最近的居民房的距離。然后在看G2 G3等等一系列加油站，看看G2 G3離最近的居民房的距離有多大，在加油站G這個(gè)維度上，選一個(gè)最大的。在枚舉單個(gè)加油站Gi的時(shí)候，選擇距離最小的。)
那么就是說(shuō)，之前d[]數(shù)組，求得就是枚舉每一個(gè)加油站，得到d[MAXV]則為G1離每個(gè)最近居民房的距離。然后在這里面，找一個(gè)最小的。這個(gè)最小的，就是該加油站與居民房的最近距離。
也可以說(shuō)，一開(kāi)始是在尋找距離某個(gè)特定加油站G最近(小)的那個(gè)居民房是多少號(hào)，距離又是多少。然后再對(duì)比每個(gè)加油站G與其最近的據(jù)民房的最近距離，這次取最大的。
代碼邏輯：
- 首先看main()函數(shù)，為了將加油站ID可以順利輸入，我們定義頂點(diǎn)編號(hào)的類型為char型數(shù)組，來(lái)表示字符串(用string應(yīng)該也可以)。
- 還是main()函數(shù)中，枚舉所有的加油站，范圍從n+1到n+m。枚舉過(guò)程中，先通過(guò)D算法求出d[]數(shù)組，也就是距離第n+i號(hào)加油站，每一個(gè)居民房與它的最短距離。然后，得到某個(gè)特定加油站的d[]數(shù)組后，再針對(duì)該加油站枚舉所有的居民房(當(dāng)然這個(gè)for循環(huán)是嵌套在上個(gè)for循環(huán)中的)。
在這第二個(gè)枚舉所有的據(jù)民房中，我們要求的是——
針對(duì)于某個(gè)特定加油站G，離其最近的居民房的距離和所有居民房與該加油站的平均距離。
跳出第二個(gè)枚舉所有居民房的循環(huán)后，這時(shí)我們已經(jīng)得到了針對(duì)于某個(gè)加油站，所有居民房與它的平均距離，還有離它最近的呢個(gè)居民房。
接下來(lái)，看的是，該加油站與所有居民房的距離中，是否有哪個(gè)居民房離它的距離大于了DS，如果有，則直接跳過(guò)該加油站，進(jìn)入下一個(gè)加油站（continue）。
如果沒(méi)有出現(xiàn)大于DS的，則更新最大的最近距離(ansDis)，如果到了后面加油站多了起來(lái)，最大的最近距離一樣，則更新最小的平均距離，誰(shuí)的平均距離最小，則選擇哪個(gè)加油站。
注意：minDis是最近距離，ansDis是最大的最近距離。因?yàn)閙inDis是求最小值，所以minDis的初值是INF。求解代碼是這樣(注意是d[j]<minDis，是小于號(hào)，看看d[j]是否小于minDis，如果小于當(dāng)前的minDis，就更新minDis)：
double minDis = INF, avg = 0;
//--更新當(dāng)前最大的最近距離--
if (d[j] < minDis) minDis = d[j];
然而，求ansDis是最大值，所以ansDis初值為-1。if判斷中，則是大于號(hào)(看看minDis是否大于ansDis，如果大于當(dāng)前的ansDis，就更新ansDis)——
double ansDis = -1, ansAvg = INF;
int ansID = -1;
//--更新最大的最近距離--
if (minDis > ansDis)
{
ansID = i;
ansDis = minDis;
ansAvg = avg;
}
完整代碼如下：
//---Dijkstra算法求所有頂點(diǎn)到起點(diǎn)s的最短距離---
void Dijkstra(int s)
{
memset(vis, false, sizeof(vis));
fill(d, d + MAXV, INF);
d[s] = 0;
for (int i = 0; i < n + m; i++)
{
int u = -1, MIN = INF;
for (int j = 1; j <= n + m; j++)
{
if (vis[j] == false && d[j] < MIN)
{
u = j;
MIN = d[j];
}
}
if (u == -1) return;
vis[u] = true;
for (int v = 1; v <= n + m; v++)
{
if (vis[v] == false && G[u][v] != INF)
{
if (d[u] + G[u][v] < d[v])
{
d[v] = d[u] + G[u][v];
}
}
}
}
}
//---將str[]轉(zhuǎn)換為數(shù)字，若str是數(shù)字，則返回本身---
//---否則，返回去掉G之后的數(shù)，并加上n---
int getID(char str[])
{
int i = 0, len = strlen(str), ID = 0;
while (i < len)
{
//--只要不是G，就轉(zhuǎn)換為數(shù)字--
if (str[i] != 'G')
{
ID = ID * 10 + (str[i] - '0');
}
i++;
}
//--首位如果是G，返回n+ID--
if (str[0] == 'G') return n + ID;
//--首位不是G，返回ID--
else return ID;
}
int main()
{
scanf("%d%d%d%d", &n, &m, &k, &DS);
//--u和v表示一條road的左右端點(diǎn)，w表示邊權(quán)--
int u, v, w;
char city1[5], city2[5]; // 這里的字符串還是用char型數(shù)組來(lái)定義的
fill(G[0], G[0] + MAXV * MAXV, INF);
for (int i = 0; i < k; i++)
{
//--以字符串的形式讀入城市編號(hào)--
scanf("%s %s %d", city1, city2, &w);
u = getID(city1);
v = getID(city2);
//--邊權(quán)--
G[v][u] = G[u][v] = w;
}
//--ansDis存放最大的最近距離--
//--ansAvg存放最小的平均距離--
//--ansID存放最終的加油站ID--
double ansDis = -1, ansAvg = INF;
int ansID = -1;
//--枚舉所有的加油站--
for (int i = n + 1; i <= n + m; i++)
{
//---minDis為當(dāng)前最大的最近距離，avg為平均距離---
double minDis = INF, avg = 0;
//---進(jìn)行Dijkstra算法，求出d[]數(shù)組---
Dijkstra(i);
//---枚舉所有據(jù)民房---
//---求出當(dāng)前的minDis和avg---
for (int j = 1; j <= n; j++)
{
//--存在距離大于DS的居民房，直接跳出--
if (d[j] > DS)
{
minDis = -1;
break;
}
//--更新當(dāng)前最大的最近距離--
if (d[j] < minDis) minDis = d[j];
//--獲取平均距離--
avg += 1.0 * d[j] / n;
}
//--如果存在距離大于DS的居民房，則跳過(guò)該加油站--
if (minDis == -1) continue;
//--更新最大的最近距離--
if (minDis > ansDis)
{
ansID = i;
ansDis = minDis;
ansAvg = avg;
}
//--更新最小平均距離--
else if (minDis == ansDis && avg < ansAvg)
{
ansID = i;
ansAvg = avg;
}
}
//--無(wú)解--
if (ansID == -1) printf("No Solution\n");
else
{
printf("G%d\n", ansID - n);
printf("%.1f %.1f\n", ansDis, ansAvg);
}
return 0;
}
這次沒(méi)有詳細(xì)說(shuō)D算法，因?yàn)镈算法這次唯二的不同就是——
- 函數(shù)的頭2步，分別是對(duì)vis[]和d[]數(shù)組的重新賦值(d[s]=0是都有的)
- 枚舉范圍是n+m
