（仿佛回到了當年打比賽的時候呢

POJ 3013（Big Christmas Tree）

傳送門：http://poj.org/problem?id=3013

題目大意：由一堆頂點和邊構造出一棵圣誕樹，1號頂點固定為樹根，頂點和邊各自有權重值（均為正數(shù)）。構造圣誕樹的邊的開銷是邊權乘以子樹中所有頂點的權重之和，總開銷則是所有邊的開銷之和。求圣誕樹的最小開銷。

稍微變換一下，容易得知構造圣誕樹的最小開銷是：

Σ ( 某頂點到1號頂點的最小距離 * 該頂點的權重值 )

故這道題是個純粹的單源最短路問題。

說起單源最短路，我們可以很快想起圖論課程一定會教的兩個經典算法，即Bellman-Ford算法和Dijkstra算法。本文只討論后者，前者（以及它的優(yōu)化版本SPFA）之后有時間再說，畢竟今天是Christmas Eve，不想寫太多咯。

樸素的Dijkstra算法

Dijkstra算法本質上是貪心+BFS的策略，即以源點為起始，不斷探測相鄰的頂點，每次都選擇當前路徑最短的那個頂點，并對該頂點的所有出邊做松弛操作，各個頂點的最短路徑就會一直擴散下去，直到所有頂點都處理完畢。

下面來描述一下它。設圖G=(V,E)是一張帶權有向圖。聲明一個數(shù)組dist，dist[v]表示當前從源點s開始到頂點v的最短路徑長度（初始化dist[s]為0，其他為無窮大）。Dijkstra算法可以用如下偽碼表示。

function dijkstra(G, s):
  // 初始化
  create vertex set V
  create current min-distance array dist[]
  foreach vertex v of G:
    add v to V
    dist[v] = INFINITY
  dist[s] = 0

  while V is not empty:
    // 選擇未處理的頂點集合V中dist最小的那個頂點
    u = vertex in V with MINIMUM dist[u]
    remove u from V
    // 遍歷所有出邊頂點
    foreach out-edge vertex v of u:
      // 松弛，其實就是判斷A經由B到C的路徑以及A直接到C的路徑哪個短
      alt_dist = dist[u] + length(u, v)
      if alt_dist < dist[v]:
        dist[v] = alt_dist

  return dist

英文維基上給了一個很好的GIF來描述Dijkstra算法的執(zhí)行過程。

需要注意，Dijkstra算法無法處理帶負權邊的圖，即邊“長度”小于0的圖。由于該算法的貪心性質，它“看不到”遠處的負權邊，所以會破壞松弛操作的正確性（加上負權邊之后本來已經確定的最短路徑就不再是最短的了），得出的結果就是錯的。特別地，如果圖里存在負權環(huán)，那么Dijkstra算法就會陷入死循環(huán)出不來。所以，只要題目里存在負權邊，我們就必須換用Bellman-Ford/SPFA算法。（沒有負權邊就別用SPFA了，SPFA已經被各種競賽卡得不要不要的了）

算法介紹完了，來學以致用，做一下上面那道圣誕樹的題目吧。代碼如下。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long ll;
const int MAXN = 50010;
const ll INF = 1e18;

int t, nv, ne, a, b, c;
int edgeNum;
int weight[MAXN];
bool visited[MAXN];
ll dist[MAXN];

struct Edge {
  int next, to, weight;
};
Edge edges[MAXN * 2];
int head[MAXN];

inline void addEdge(int from, int to, int weight) {
  edges[++edgeNum].weight = weight;
  edges[edgeNum].to = to;
  edges[edgeNum].next = head[from];
  head[from] = edgeNum;

  edges[++edgeNum].weight = weight;
  edges[edgeNum].to = from;
  edges[edgeNum].next = head[to];
  head[to] = edgeNum;
}

void dijkstra() {
  for (int i = 0; i <= nv; i++) {
    dist[i] = INF;
  }
  dist[1] = 0;
  memset(visited, 0, sizeof(visited));

  for (int i = 1; i <= nv; i++) {
    int u = -1;
    ll minDist = INF;
    for (int j = 1; j <= nv; j++) {
      if (!visited[j] && dist[j] < minDist) {
        minDist = dist[j];
        u = j;
      }
    }
    if (u == -1) {
      break;
    }
    visited[u] = true;

    for (int e = head[u]; e != 0; e = edges[e].next) {
      int v = edges[e].to;
      if (!visited[v] && dist[u] + edges[e].weight < dist[v]) {
        dist[v] = dist[u] + edges[e].weight;
      }
    }
  }
}

int main() {
  scanf("%d", &t);
  while (t--) {
    memset(head, 0, sizeof(head));
    edgeNum = 0;
    scanf("%d%d", &nv, &ne);
    for (int i = 1; i <= nv; i++) {
      scanf("%d", &weight[i]);
    }
    for (int i = 1; i <= ne; i++) {
      scanf("%d%d%d", &a, &b, &c);
      addEdge(a, b, c);
    }

    dijkstra();

    ll result = 0;
    for (int i = 1; i <= nv; i++) {
      if (dist[i] == INF) {
        result = -1;
        break;
      }
      result += weight[i] * dist[i];
    }
    if (result == -1) {
      printf("No Answer\n");
    } else {
      printf("%lld\n", result);
    }
  }
  return 0;
}

由于邊的花費和節(jié)點的權重值都能達到2¹⁶，所以dist數(shù)組和結果值要乖乖用long long。另外，這里采用鏈式前向星來存儲圖，它是一種介于鄰接表和鄰接矩陣之間的結構，在競賽中很常用。關于鏈式前向星的細節(jié)請參考原作者Malash的這篇文章（orz）。

好了，提交一下。恭喜~我們得到了華麗麗熱氣騰騰的TLE。

從樸素Dijkstra算法的實現(xiàn)可知，它的時間復雜度是O(|E|+|V|²)=O(|V|²)。而題目給出的|V|最大可達50000，時間限制為3000ms，顯然是非常緊張的。所以不管是在競賽中還是在實際應用中，都會對樸素Dijkstra算法做優(yōu)化，下面來看。

最小堆優(yōu)化的Dijkstra算法

重新看一下上面的代碼，可以發(fā)現(xiàn)遍歷頂點并找出dist最小的點的過程效率很低，就是下面這一小段。

  for (int i = 1; i <= nv; i++) {
    int u = -1;
    ll minDist = INF;
    for (int j = 1; j <= nv; j++) {
      if (!visited[j] && dist[j] < minDist) {
        minDist = dist[j];
        u = j;
      }
    }
    // ....

那么能不能維護住這些dist最小的點，不必每次都去O(n²)地掃呢？答案自然是可以的，用最小堆就完事了，C++ STL自帶有優(yōu)先隊列priority_queue?？垂倏梢蚤喿x筆者之前寫的《二叉堆、優(yōu)先隊列與Top-N問題》這篇文章獲得一點基礎知識。

具體實現(xiàn)起來，還有兩點要注意：

• 要維護好頂點下標到dist值的映射；
• C++的priority_queue與Java的PriorityQueue相反，默認是最大堆。

我們可以定義頂點下標與dist值的結構體，并重載<運算符使其變成最小堆，如下。

struct QNode {
  int vno, dist;
  bool operator < (const QNode &x) const {
    return x.dist < dist;
  }
};

接下來改寫dijkstra()方法，輕松愉快了。將原版那個耗時的for循環(huán)換成從優(yōu)先隊列中pop出dist值最小的頂點，其他一切照常。

#include <queue>

void dijkstra() {
  priority_queue<QNode> q;
  for (int i = 0; i <= nv; i++) {
    dist[i] = INF;
  }
  dist[1] = 0;
  memset(visited, 0, sizeof(visited));

  QNode tn, qn;
  tn.vno = 1;
  tn.dist = 0;
  q.push(tn);

  while (!q.empty()) {
    tn = q.top();
    q.pop();
    int u = tn.vno;
    if (visited[u]) {
      continue;
    }
    visited[u] = true;

    for (int e = head[u]; e != 0; e = edges[e].next) {
      int v = edges[e].to;
      if (!visited[v] && dist[u] + edges[e].weight < dist[v]) {
        dist[v] = dist[u] + edges[e].weight;
        qn.vno = v;
        qn.dist = dist[v];
        q.push(qn);
      }
    }
  }
}

提交，成功AC。

最小堆優(yōu)化的Dijkstra算法時間復雜度可以改進到O[(|E|+|V|)log|V|]，對于稀疏圖（即|E| << |V|²的圖）尤為有效。

事實上，除了用最小堆優(yōu)化Dijkstra算法之外，斐波那契堆、配對堆也都可以，并且效率會更高。但最小堆一般都夠用了，并且筆者之前沒有介紹過斐波那契堆和配對堆，它們倆還是有點難理解的，因此就不強行在這里講了，擇日介紹吧。

The End

Happy Christmas Eve~

民那晚安晚安。