1) Bellman Ford算法找負(fù)環(huán)的應(yīng)用.
#include?<cstdio>
#include?<cstdlib>
#include?<queue>
#include?<deque>
using?namespace?std;
struct?Node?
{
????int?to;
????int?weight;
????Node?*next;
};
#define?MAXFIELD?(1000?+?10)
#define?MAXPATH?(2500?+?10)
#define?MAXWORMHOLE?(200?+?10)
Node?nodeHead[MAXFIELD];
Node?nodes[MAXPATH?*?2?+?MAXWORMHOLE];
int?dis[MAXFIELD?+?1];
bool?isInQueue[MAXFIELD?+?1];
int?allocPos?=?0;
Node?*getNode()?{
????return?nodes?+?allocPos++;
}
void?initGraph(int?n)?{
????allocPos?=?0;
????int?i?=?0;
????for?(i?=?0;?i?<?n;?++i)?{
????????nodeHead[i].next?=?NULL;
????????dis[i]?=?0;
????}
}
void?addEdge(int?from,?int?to,?int?timeNeed)?{
????Node?*newNode?=?getNode();
????newNode->next?=?nodeHead[from].next;
????newNode->to?=?to;
????newNode->weight?=?timeNeed;
????nodeHead[from].next?=?newNode;
}
int?main()?{
????int?caseCount,?fieldCount,?pathCount,?wormHoleCount;
????int?i,?j,?from,?to,?timeNeed;
????scanf("%d",?&caseCount);
????for?(i?=?0;?i?<?caseCount;?i++)?{
????????scanf("%d%d%d",?&fieldCount,?&pathCount,?&wormHoleCount);
????????initGraph(fieldCount?+?1);
????????for?(j?=?0;?j?<?pathCount;?j++)?{
????????????scanf("%d%d%d",?&from,?&to,?&timeNeed);
????????????addEdge(from,?to,?timeNeed);
????????????addEdge(to,?from,?timeNeed);
????????}
????????for?(j?=?0;?j?<?wormHoleCount;?++j)?{
????????????scanf("%d%d%d",?&from,?&to,?&timeNeed);
????????????addEdge(from,?to,?-timeNeed);
????????}
????????//?關(guān)鍵:?按照題目的要求,?可以看出是找圖中有沒(méi)有負(fù)環(huán)
????????//?引入一個(gè)超級(jí)點(diǎn)s,?s能夠到達(dá)任意一個(gè)field,?但是沒(méi)有任何field能夠到達(dá)s
????????//?然后如果圖中不存在負(fù)環(huán),?則在經(jīng)過(guò)fieldCount次松弛(我叫優(yōu)化)以后,?
????????//?就沒(méi)有辦法使任意一個(gè)field節(jié)點(diǎn)的權(quán)值變小了,?而如果存在負(fù)環(huán),?
????????//?則還能松弛/優(yōu)化.
????????//?這就是為什么初始化時(shí)需要把所有的field都?jí)喝腙?duì)列.
????????deque<int>?q;
????????for?(j?=?1;?j?<=?fieldCount;?++j)?{
????????????q.push_back(j);
????????????isInQueue[j]?=?true;
????????}
????????bool?answer?=?false;
????????int?round?=?0;
????????while?(!q.empty())?{
????????????int?n?=?q.size();
????????????for?(j?=?0;?j?<?n;?j++)?{
????????????????int?u?=?q.front();
????????????????q.pop_front();
????????????????isInQueue[u]?=?false;
????????????????Node?*tra;
????????????????for?(tra?=?nodeHead[u].next;?tra?!=?NULL;?tra?=?tra->next)?{
????????????????????int?temp?=?tra->weight?+?dis[u];
????????????????????if?(temp?<?dis[tra->to])?{
????????????????????????dis[tra->to]?=?temp;
????????????????????????if?(!isInQueue[tra->to])?{
????????????????????????????q.push_back(tra->to);
????????????????????????????isInQueue[tra->to]?=?true;
????????????????????????}
????????????????????}
????????????????}
????????????}
????????????round++;
????????????if?(round?>?fieldCount)?{
????????????????answer?=?true;
????????????????q.clear();
????????????????break;
????????????}
????????}
????????if?(answer)?{
????????????puts("YES");
????????}
????????else?{
????????????puts("NO");
????????}
????}
????return?0;
}
Dijkstra 未優(yōu)化版, 算法相對(duì)清晰:
// 關(guān)鍵1: 處理每個(gè)人的地位等級(jí)
// 辦法: 枚舉--假設(shè)某種方案是最省錢的,
// 則該方案中的所有交易者的地位等級(jí)都會(huì)落在一個(gè)寬度為rankLimit的區(qū)間
// 于是可以枚舉這個(gè)區(qū)間:
// [ownerRank[1] - rankLimit, ownerRank] ~ [ownerRank[1], ownerRank + rankLimit]
// 于是這道題考察了最短路的dijkstra算法與枚舉的結(jié)合.
//
// 其中枚舉可行是需要考察其復(fù)雜度的:
// dijkstra算法的復(fù)雜度為: O(n * n), n為節(jié)點(diǎn)數(shù)目
// 枚舉量為 rankLimit + 1;
// 于是枚舉 + dijkstra的算法復(fù)雜度為 O(n * n) * (rankLimit + 1)
// 關(guān)鍵2: 由題意要聯(lián)想到用最短路, 而且是邊權(quán)為正的最短路
// 1) 以物品為圖節(jié)點(diǎn)
// 2) 設(shè)i物品如果能用j物品以價(jià)格m交換, 則邊(i,j)的權(quán)值為m
// 3) 設(shè)求得節(jié)點(diǎn)1到物品x的最短路, 該最短路的權(quán)值和為tw(total weight的縮寫),
// 則從物品x開(kāi)始物物交換的所有方案中, 最節(jié)省的方案會(huì)耗費(fèi)tw + price[x]的金錢
// 而婚禮最少需要的金幣數(shù)就是所有 1 <= x <= goodsCount 中,
// tw[1][x] + price[x]最小的那個(gè). (tw[1][x]表示1到x的最短路徑權(quán)值)
// 優(yōu)化1: 在dijkstra算法的代碼部分, 需要對(duì)原點(diǎn)到節(jié)點(diǎn)的最小距離是否已知作出判斷.
// 這個(gè)判斷是用bool數(shù)組disKnown來(lái)判斷的, 浪費(fèi)大量時(shí)間.
// 可以優(yōu)化為添加一個(gè)數(shù)組, 用該數(shù)組保存最小距離未知的節(jié)點(diǎn)的編號(hào).
// 只處理數(shù)組中的節(jié)點(diǎn).
#include <cstdio>
using namespace std;
struct Node {
int to;
int weight;
Node *next;
};
#define INF (1 << 30)
#define MAXNODE (100 + 10)
#define MAXEDGE (MAXNODE * MAXNODE + 10)
Node nodeHead[MAXNODE + 1];
Node nodes[MAXEDGE];
int ownerRank[MAXNODE + 1];
int price[MAXNODE + 1];
int minWeight[MAXNODE + 1];
bool disKnown[MAXNODE + 1];
int allocPos = 0;
Node *getNode() {
return nodes + allocPos++;
}
void initGraph(int n) {
allocPos = 0;
int i = 0;
for (i = 0; i < n; ++i) {
nodeHead[i].next = NULL;
minWeight[i] = INF;
}
}
void addEdge(int from, int to, int weight) {
Node *newNode = getNode();
newNode->next = nodeHead[from].next;
newNode->to = to;
newNode->weight = weight;
nodeHead[from].next = newNode;
}
int main() {
int rankLimit, goodsCount, substituteCount, subPrice, num, minPrice, minWei;
int minWeiPos;
int i, j, rankStart;
scanf("%d%d", &rankLimit, &goodsCount);
initGraph(goodsCount + 1);
for (i = 1; i <= goodsCount; ++i) {
scanf("%d%d%d", price + i, ownerRank + i, &substituteCount);
for (j = 0; j < substituteCount; ++j) {
scanf("%d%d", &num, &subPrice);
addEdge(i, num, subPrice);
}
}
minPrice = price[1];
for (rankStart = ownerRank[1] - rankLimit; rankStart <= ownerRank[1]; rankStart++) {
for (i = 1; i <= goodsCount; ++i) {
minWeight[i] = INF;
// 如果某個(gè)節(jié)點(diǎn)/商品擁有者的階級(jí)地位不在[rankStart, rankStart + rankLimit]
// 的范圍內(nèi), 就不必考慮該節(jié)點(diǎn)
if (ownerRank[i] < rankStart || ownerRank[i] > rankStart + rankLimit) {
disKnown[i] = true;
}
else {
disKnown[i] = false;
}
}
disKnown[1] = false;
minWeight[1] = 0;
for (i = 1; i <= goodsCount; ++i) {
minWei = INF;
for (j = 1; j <= goodsCount; ++j) {
if (!disKnown[j] && minWeight[j] < minWei) {
minWei = minWeight[j];
minWeiPos = j;
}
}
disKnown[minWeiPos] = true;
if (minWei + price[minWeiPos] < minPrice) {
minPrice = minWei + price[minWeiPos];
}
for (Node *tra = nodeHead[minWeiPos].next; tra != NULL; tra = tra->next) {
if (!disKnown[tra->to] &&
minWeight[tra->to] > minWeight[minWeiPos] + tra->weight ) {
minWeight[tra->to] = minWeight[minWeiPos] + tra->weight;
}
}
}
}
printf("%d\n", minPrice);
return 0;
}
優(yōu)化后, 速度要快一些, 但是代碼比較難看, 對(duì)變量的命名讓人比較惱火:
#include <cstdio>
using namespace std;
struct Node {
int to;
int weight;
Node *next;
};
#define INF (1 << 30)
#define MAXNODE (100 + 10)
#define MAXEDGE (MAXNODE * MAXNODE + 10)
Node nodeHead[MAXNODE + 1];
Node nodes[MAXEDGE];
int ownerRank[MAXNODE + 1];
int price[MAXNODE + 1];
int minWeight[MAXNODE + 1];
int distanceUnknown[MAXNODE + 1];
int distanceUnknownCount;
bool isDistanceKnown[MAXNODE + 1];
int allocPos = 0;
Node *getNode() {
return nodes + allocPos++;
}
void initGraph(int n) {
allocPos = 0;
int i = 0;
for (i = 0; i < n; ++i) {
nodeHead[i].next = NULL;
minWeight[i] = INF;
}
}
void addEdge(int from, int to, int weight) {
Node *newNode = getNode();
newNode->next = nodeHead[from].next;
newNode->to = to;
newNode->weight = weight;
nodeHead[from].next = newNode;
}
int main() {
int rankLimit, goodsCount, substituteCount, subPrice, num, minPrice, minWei;
int minWeiDisUnkPos;
int i, j, from;
scanf("%d%d", &rankLimit, &goodsCount);
initGraph(goodsCount + 1);
for (i = 1; i <= goodsCount; ++i) {
scanf("%d%d%d", price + i, ownerRank + i, &substituteCount);
for (j = 0; j < substituteCount; ++j) {
scanf("%d%d", &num, &subPrice);
addEdge(i, num, subPrice);
}
}
minPrice = price[1];
for (from = ownerRank[1] - rankLimit; from <= ownerRank[1]; from++) {
for (i = 1; i <= goodsCount; ++i) {
minWeight[i] = INF;
}
distanceUnknownCount = 0;
for (i = 1; i <= goodsCount; ++i) {
if (ownerRank[i] >= from && ownerRank[i] <= from + rankLimit) {
distanceUnknown[distanceUnknownCount++] = i;
isDistanceKnown[i] = false;
}
else {
isDistanceKnown[i] = true;
}
}
minWeight[1] = 0;
isDistanceKnown[1] = false;
int n = distanceUnknownCount;
for (i = 0; i < n; ++i) {
minWei = INF;
for (j = 0; j < distanceUnknownCount; ++j) {
if (minWeight[ distanceUnknown[j] ] < minWei) {
minWei = minWeight[ distanceUnknown[j] ];
minWeiDisUnkPos = j;
}
}
if (minWei + price[ distanceUnknown[minWeiDisUnkPos] ] < minPrice) {
minPrice = minWei + price[ distanceUnknown[minWeiDisUnkPos] ];
}
for (Node *tra = nodeHead[ distanceUnknown[minWeiDisUnkPos] ].next; tra != NULL; tra = tra->next) {
if (!isDistanceKnown[tra->to] &&
minWeight[tra->to] > minWeight[ distanceUnknown[minWeiDisUnkPos] ] + tra->weight ) {
minWeight[tra->to] = minWeight[ distanceUnknown[minWeiDisUnkPos] ] + tra->weight;
}
}
isDistanceKnown[ distanceUnknown[minWeiDisUnkPos] ] = true;
distanceUnknown[minWeiDisUnkPos] = distanceUnknown[--distanceUnknownCount];
}
}
printf("%d\n", minPrice);
return 0;
}
摘要: 1) 實(shí)質(zhì)就是是確定圖中是否存在正環(huán)--沿著這個(gè)環(huán)一直走能夠使環(huán)內(nèi)節(jié)點(diǎn)的權(quán)值無(wú)限增長(zhǎng).2) 特點(diǎn)是: 每個(gè)邊的權(quán)值是動(dòng)態(tài)變化的, 這點(diǎn)提醒我們適合用Bellman Ford算法來(lái)處理(SPFA實(shí)質(zhì)上是Bellman Ford的優(yōu)化, 算法思想是一樣的).SPFA算法:
Code highlighting produced by Actipro CodeHighlighter (freeware...
閱讀全文